2022 CCPC guangzhou M-526互联

// woshinidiea nizhemeexinwo ^ ^
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
//const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
/*
 因为是所有数的异或和 我们考虑拆位来看
 又因为有m的限制 所以考虑数位dp
 我们设置有当前为第i位 我们有s个卡住上届 现在的为now的方案数
 因为limit的改变 我们可以直接枚举 有多少个为1 多少个为0
 最后的now会很大 所以我们要剪枝 然后状态数其实变得很少
*/
int n,m,k,a[N],b[N],c[41];
map<int,int>f[41][19];
int qmi(int a, int k,int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}
int inv(int x){return qmi(x,mod-2,mod);}
int C(int x, int y) {
    if (x < 0 || y < 0 || x < y) return 0;
    return a[x] * b[y] % mod * b[x-y] % mod;
}
void init() {
    a[0] = b[0] = 1;
    for (int i = 1; i < N; i ++ )a[i] = a[i - 1] * i % mod;
    b[N - 1] = qmi(a[N - 1], mod - 2 , mod);
    for (int i = N - 2; i >= 0; i -- )b[i] = b[i + 1] * (i + 1) % mod;
}
int dfs(int pos,int s,int now){
    if(now > n)
        return 0;
    if(pos==-1){
        return (now==n);
    }
    int n1 = k / 2, n0 = k - n1;
    if (now + ((1LL << pos + 1) - 1) * n1 * n0 < n)
        return 0;
    if(f[pos][s].count(now))return f[pos][s][now];
    int res=0;
    if(c[pos]){
        for(int i=0;i<=s;i++){
            for(int j=0;j<=k-s;j++){
                int val=(1ll<<pos)*(i+j)*(k-i-j);
                int tmp=C(s,i)*C(k-s,j)%mod;
                (res+=tmp*dfs(pos-1,i,now+val)%mod)%=mod;
            }
        }
    }else{
        for(int i=0;i<=k-s;i++){
            int val=(1ll<<pos)*(i)*(k-i);
            int tmp=C(k-s,i);
            (res+=tmp*dfs(pos-1,s,now+val)%mod)%=mod;
        }
    }
    return f[pos][s][now]=res;
}
int dp(int x){
    int len=0;
    while(x){
        c[len++]=x%2;
        x/=2;
    }
    return dfs(len-1,k,0);
}
void solve() {
    cin>>n>>m>>k;
    cout<<dp(m)<<endl;
}
signed main(){
    fast
    int t;t=1;//cin>>t;
    init();
    while(t--) {
        solve();
    }
}