#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#define BUG puts("no bug")
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define REP(a,b,c) for(ll a=b;a<=c;a++)
#define PER(a,b,c) for(ll a=b;a>=c;a--)
#define ll long long
#define lb(a) (a&(-a))
using namespace std;
const ll MAXN=66;
ll n,m,t,k,mod=1000000003LL;
ll digit[MAXN];
ll dp[MAXN][MAXN][2];
ll power[MAXN];
ll solve(ll i,ll pre,ll len)
{
    ll tmp=0,ans=0;
    pre&=(~((1<<len)-1));
    if(i==n+1)return !pre;
    ll kk=pre&(1<<len)?1:0;
    if(dp[i][len][kk]!=-1)return dp[i][len][kk];

    PER(j,31,0)
    {
        if(digit[i]&(1<<j))ans=(ans+solve(i+1,pre^tmp,max(len,j))*power[min(len,j)])%mod,tmp|=(1<<j);
    }
    return dp[i][len][kk]=ans;
}
int main()
{
    power[0]=1;
    REP(i,1,MAXN-1)power[i]=(power[i-1]*2)%mod;
    while(cin>>n>>m&&(n||m))
    {
        REP(i,1,n)cin>>digit[i],digit[i]++;
        memset(dp,-1,sizeof dp);
        cout<<solve(1,m,0)<<endl;
    }
}
