#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

typedef long long ll;

int n,k,tot,s[70];

ll ans,v[1010];

int f[70],mark[70];

int find(int x)

{

	return (f[x]==x)?x:(f[x]=find(f[x]));

}

bool check(int a,int b)

{

	for(int i=1;i<=n;i++)	if(((v[i]>>a-1)^(v[i]>>b-1))&1)	return 0;

	return 1;

}

ll calc(ll x)

{

	if(++x>=(1ll<<k))	return (1ll<<s[k]);

	int i;

	ans=0;

	memset(mark,-1,sizeof(mark));

	for(i=k;i;i--)

	{

		if(x&(1ll<<i-1))

		{

			if(mark[f[i]]!=1)	ans+=1ll<<s[i-1];

			if(f[i]==i)	mark[i]=1;

			if(mark[f[i]]==0)	break;

		}

		else

		{

			if(f[i]==i)	mark[i]=0;

			if(mark[f[i]]==1)	break;

		}

	}

	return ans;

}

int main()

{

	int j;

	ll i,l,r;

	scanf("%d%d%lld%lld",&n,&k,&l,&r);

	for(i=1;i<=n;i++)	scanf("%lld",&v[i]);

	for(i=1;i<=k;i++)

	{

		f[i]=i;

		for(j=i-1;j;j--)	if(check(i,j)&&find(i)!=find(j))	f[f[j]]=f[i];

	}

	for(i=1;i<=k;i++)

	{

		s[i]=s[i-1];

		if(find(i)==i)	s[i]++;

	}

	printf("%lld",calc(r)-calc(l-1));

	return 0;

}