#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;
const int N=1e3+5;
const int MOD=1e9+7;
int pp[N];
int can[N];
int t1[N];
int len=0;
map<pair<pair<int,int>,int >,int>mp;
int C[N][N];
int work(int bit,int rem,int cnt){
	//cout<<bit<<" "<<rem<<" "<<cnt<<"\n";
	//cout<<"?\n";
	if(rem>k/2*(k-k/2)*(pp[bit+1]-1))return 0;
	if(rem<0)return 0;
	if(bit==0){
		int x=(m&1);
		if(t1[rem]==-1)return 0;
		if(x==0){
			if(t1[rem]*2!=k)return (C[k-cnt][t1[rem]]+C[k-cnt][k-t1[rem]])%MOD;
			else return C[k-cnt][t1[rem]];
		}
		else{
			if(t1[rem]*2!=k)return C[k][t1[rem]]*2%MOD;
			else return C[k][t1[rem]];
		}
	}
	if(mp[make_pair(make_pair(bit,rem),cnt)])return mp[make_pair(make_pair(bit,rem),cnt)];
	int x=(m&(pp[bit+1]-1));
	int ans=0;
	if(m&pp[bit]){
		for(int i=0;i<=k;i++){
			int limit=min(cnt,i);
			int tt=can[min(i,k-i)]*pp[bit];
			for(int j=0;j<=limit;j++){
				//cout<<i<<" "<<j<<" "<<C[cnt][j]%MOD*C[k-cnt][i-j]%MOD<<"\n";
				ans+=work(bit-1,rem-tt,j)*C[cnt][j]%MOD*C[k-cnt][i-j]%MOD;
				ans%=MOD;
			}
		}
	}
	else{
		for(int i=0;i<=k-cnt;i++){
			int tt=can[min(i,k-i)]*pp[bit];
			ans+=work(bit-1,rem-tt,cnt);
			ans%=MOD;
		}
	}
	mp[make_pair(make_pair(bit,rem),cnt)]=ans;
	//cout<<bit<<" "<<rem<<" "<<cnt<<":"<<ans<<"\n"; 	
	return ans;
} 
signed main(){
	C[0][0]=1;
	C[1][1]=1;
	C[1][0]=1;
	for(int i=2;i<=52;i++){
		for(int j=0;j<=i;j++){
			if(!j)C[i][j]=1;
			else C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
			//cout<<i<<" "<<j<<" "<<C[i][j]<<"\n"; 
		}
	}
	pp[0]=1;
	for(int i=1;i<=52;i++)pp[i]=pp[i-1]<<1;
	scanf("%lld%lld%lld",&n,&m,&k);
	if(k==1){
		cout<<(m+1)*(n==0)%MOD<<"\n";
		return 0;
	}
	for(int i=0;i<=k*k;i++)t1[i]=-1;
	for(int i=0;i<=k/2;i++){
		can[len++]=i*(k-i);
		t1[i*(k-i)]=i;
	}
	cout<<work(45,n,k)<<"\n";
	return 0;
}