#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,maxn=25;
int f[65][1035][20],n,m,K,C[maxn][maxn];

signed main()
{
	cin>>n>>m>>K;
	f[50][0][K]=1;
	C[0][0]=1;
	for(int i=1;i<=K;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=K;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
//	cerr<<"OK\n";
	for(int i=50;i>0;i--)
	{
		for(int j=0;j<=1024;j++)
		{
			for(int k=0;k<=K;k++)
			{
				if(f[i][j][k]==0)
					continue;
				for(int t=0;t<=K;t++)
				{
					int tarj=n>>i-1&1;
					tarj+=j<<1;
					int now=t*(K-t);
					tarj-=now;
					if(tarj<0||tarj>6)
						continue;
//					cerr<<i<<' '<<j<<' '<<k<<' '<<f[i][j][k]<<' '<<t<<' '<<tarj<<' '<<now<<'\n';
//					cerr<<i<<' '<<j<<' '<<k<<'\n';
					if((1ll<<i-1&m)==0)
					{
						if(K-k<t)
							continue;
//						cerr<<K-k<<' '<<"QWQ\n";
						(f[i-1][tarj][k]+=C[K-k][t]*f[i][j][k]%mod)%=mod;
//						cerr<<"OK\n";
						continue;
					}
					for(int l=0;l<=k;l++)
					{
						if(l+K-k<t||l>t)
							continue;
						(f[i-1][tarj][l]+=C[k][l]*C[K-k][t-l]%mod*f[i][j][k]%mod)%=mod;
//						cerr<<l<<' '<<f[i-1][tarj][l]<<' '<<C[k][l]<<' '<<C[K-k][t-l]<<'\n';
					}
				}
			}
		}
	}
	int s=0;
	for(int i=0;i<=n;i++)
		(s+=f[0][0][i])%=mod;
	cout<<s;
	return 0;
}