meet_in_the_middle, xor Path

void solve() {
    ll n,m,k;cin>>n>>m>>k;
   // total number of moves == distance bet n-1,m-1 and 0,0 i.e n+m-2
    // 2^(n+m-1) possible choises total
    vector<vector<ll>>grid(n,vector<ll>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    vector<vector<map<ll,ll>>>left(n,vector<map<ll,ll>>(m));
    ll ans=0;
    int left_moves=(n+m-2)/2;
    for(int i=0;i<(1<<left_moves);i++){
        int r=0,c=0;
        bool in_grid=true;
        ll xor_sum=grid[0][0];
        for(int j=0;j<left_moves;j++){
            if(i&(1<<j)){
                r++;
            }else{
                c++;
            }
            if(r>=n||c>=m){
                in_grid=true;
                break;
            }
            xor_sum=xor_sum^(grid[r][c]);
        }
        if(in_grid){
           left[r][c][xor_sum]++;
        }
    }
  int right_moves=(n+m-2)-left_moves-1;
  for(int i=0;i<(1<<right_moves);i++){
    int r=n-1,c=m-1;
    ll xor_sum=grid[n-1][m-1];
    bool in_grid=true;
    for(int j=0;j<right_moves;j++){
     if(i&(1<<j)){
        r--;
     }else{
        c--;
     }
     if(r<0||c<0){
        in_grid=false;
        break;
     }
     xor_sum=xor_sum^grid[r][c];
    }
    if(in_grid){
        ll need=xor_sum^k;
        if(r>0){
            ans+=left[r-1][c][need];
        }
        if(c>0){
            ans+=left[r][c-1][need];
        }
    }
  }
  cout<<ans<<endl;
}