#include<stdio.h>
#include<string.h>
#include<unordered_map>
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int word;
typedef unsigned char byte;
struct READ{
	char c,w;
	inline READ(){c=getchar();}
	template<typename type>
	inline READ& operator>>(type &num){
		for(w=1;'0'>c||c>'9';c=getchar())
			w=c=='-'? -1:1;
		for(num=0;'0'<=c&&c<='9';c=getchar())
			num=num*10+(c-'0');
		return num*=w,*this;
	}
}cin;
const word mod=1e9+7;
ull n,m;
byte k;
word C[42][42];
gp_hash_table<ull,word> mp[42][20];
// dp[i][j][n] i 
int main(){
	cin>>n>>m>>k;
	mp[40][k][0]=1;
	C[0][0]=1;
	for(word n=1;n<=40;++n){
		C[n][0]=1;
		for(word m=1;m<=n;++m)
			C[n][m]=(C[n-1][m]+C[n-1][m-1])%mod;
	}
		
	for(word now=40;now--;) if(m>>now&1){
		for(word x=0;x<=k;++x)//x 个数贴着
			for(const auto &p:mp[now+1][x])
				for(word a=0;a<=k;++a){
					const ull nxt=p.first+(1ull*a*(k-a)<<now);
					if(nxt<=n&&n-nxt<(81<<now)) for(word y=0;y<=a&&y<=x;++y)//y个数为 1（仍然贴着）
						mp[now][y][nxt]=(1ull*C[x][y]*C[k-x][a-y]%mod
							*p.second+mp[now][y][nxt])%mod;
				}
	}else{
		for(word x=0;x<=k;++x)
			for(const auto &p:mp[now+1][x])
				for(word a=0;a<=k-x;++a){
					const ull nxt=p.first+(1ull*a*(k-a)<<now);
					if(nxt<=n&&n-nxt<(81<<now)) mp[now][x][nxt]=(
						1ull*C[k-x][a]*p.second+mp[now][x][nxt])%mod;
				}
	}
	ull ans=0;
	for(word x=0;x<=k;++x)
		ans+=mp[0][x][n];
	printf("%llu",ans%mod);
	return 0;
}