#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T>void chkmax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,const T&y){if(y<x)x=y;}

#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define mem(x) memset((x),0,sizeof(x))

typedef double db;
typedef long long ll;
typedef vector<int>vi;
typedef pair<int,int>pii;

typedef unsigned u32;
typedef unsigned uint;
typedef unsigned long long u64;

namespace orzjk{
  const int SZ=1e6;
  char buf[SZ],*p1=buf,*p2=buf;
  char nc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++;
  }
  char fub[SZ],*p3=fub,*p4=fub+SZ;
  void pc(char c){
    p3==p4&&(fwrite(fub,1,SZ,stdout),p3=fub);
    *p3++=c;
  }
  void flush(){
    fwrite(fub,1,p3-fub,stdout),p3=fub;
  }
}
using orzjk::nc;
using orzjk::pc;

//#define nc getchar
//#define pc putchar

int read(){
  int x=0,f=1;char c=nc();
  while(c<48)c=='-'&&(f=-1),c=nc();
  while(c>47)x=x*10+(c^48),c=nc();
  return x*f;
}
template<class T>void write(T x){
  static char st[41];
  if(!x)return pc(48),void();
  char*p=st;
  if(x<0)x=-x,pc('-');
  for(;x;x/=10)*p++=x%10|48;
  do{
    pc(*--p);
  }while(p!=st);
}

struct node{
  uint s0,s1;
}c[1<<23];
node operator+(const node&A,const node&B){
  return{A.s0+B.s0,A.s1+B.s1};
}

void c_add(int pos,node o){
  pos++;
  for(;pos<1<<23;pos+=pos&-pos)c[pos]=c[pos]+o;
}
node c_ask(int pos){
  pos++;
  node res={0,0};
  for(;pos;pos&=pos-1)res=res+c[pos];
  return res;
}

int tot,h[1<<23],nxt[1<<20],key[1<<20];
node val[1<<20];

void add(int pos,node o){
  c_add(pos>>7,o);
  for(int i=h[pos>>7];i;i=nxt[i]){
    if(key[i]==pos){
      val[i]=val[i]+o;return;
    }
  }
  key[++tot]=pos,val[tot]=o,nxt[tot]=h[pos>>7],h[pos>>7]=tot;
}
node ask(int pos){
  node res={0,0};
  if(pos>>7){
    res=c_ask((pos>>7)-1);
  }
  for(int i=h[pos>>7];i;i=nxt[i]){
    if(key[i]<=pos){
      res=res+val[i];
    }
  }
  return res;
}

void solve(){
  uint n,m;
  n=read(),m=read();
  uint las=0;
  for(uint i=1;i<=n;i++){
    uint l,r;
    l=Rnd()%(1<<m);
    r=Rnd()%(1<<m);
    l=(l+las)%(1<<m);
    r=(l+las)%(1<<m);
    if(l>r)swap(l,r);
    
    add(l,{i,i*l});
    if(r<(1u<<m)-1)add(r+1,{-i,-i*(r+1)});
    
    node o=ask(r);
    las+=o.s0*(r+1)-o.s1;
    if(l>0){
      o=ask(l-1);
      las-=o.s0*l-o.s1;
    }
//    cout<<las<<endl;
  }
  cout<<las%(1u<<30)<<endl;
}

signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  int T;cin>>T;while(T--)solve();
  solve();
  orzjk::flush();
  return 0;
}