QUESTION

This problem is about a little pig named Benny. Benny was given an array of N integers and another separate integer X. \n\nBenny has to find the number of subsets (not necessarily contiguous) of A such that Bitwise XOR of all elements contained within the subset evaluates to X.\n\nProbably, you have already guessed that she missed a lot of classes and is not able to solve her homework now. Therefore, she asks you to help her. Find the number of subsets of A such that Bitwise XOR of all elements of the subset will be equal to X.\n\nInput format\n\nThe first line of the input contains two space separated integers, \nN and X.\n\nThe next line contains N integers denoting the array A.\n\nOutput format\n\nPrint in a single line an answer to the problem. As the answer might be large, output it modulo 10^7 + 7.\n\nConstraints\n\n1 <= N <= 10^3\n0 <= Ai <= 2^20.

ANSWER

#include<bits/stdc++.h>
#define up(j,k,i) for(i=j;i<k;i++)
#define down(j,k,i) for(i=j;i>k;i--)
#define M 10000007
#define pp(n) printf("%lld\n",ll(n))
#define ps(n) printf("%lld ",ll(n))
#define pd(x,y) printf("%lld %lld\n",ll(x),ll(y))
#define is(n) scanf("%lld",&n)
#define max(x,y) max(ll(x),ll(y))
#define min(x,y) min(ll(x),ll(y))
#define inf LLONG_MAX
#define id(n,m) scanf("%lld%lld",&n,&m)
#define it(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define ss(s) scanf("%s",s)
#define cool 0
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pll pair<ll,ll> 
#define db cout<<"######\n"
#define null(a) memset(a,0,sizeof(a))
#define neg(a) memset(a,255,sizeof(a))
typedef long double ld;
typedef long long int ll;
using namespace std;
ll i,j,k,z,t,n,m,sum,ans,x,y,maxm=0,minm=inf;
vector<ll> v;
ll a[1005];
ll dp[1005][2058];
int main()
{
id(n,y);
up(1,n+1,i)
{
 is(x);
 if(x>=(1LL<<11))
 v.pb(x);
 else
 a[++m]=x;
}
dp[0][0]=1;
 
up(1,m+1,i)
up(0,2048,j)
dp[i][j]=(dp[i-1][j]+dp[i-1][j^a[i]])%M;
 
map<ll,ll> big;
ll mask;
z=v.size();
 
for(mask=0;mask<(1LL<<z);mask++)
{
 ll fin=0;
 up(0,z,i)
 if(mask & (1LL<<i))
  fin^=v[i];
 big[fin]=(big[fin]+1)%M;
}
up(0,2048,i)
ans=(ans+dp[m][i]*big[y^i]%M)%M;
 
pp(ans);
}