#include <bits/stdc++.h>
#define FileIO_(file) \
    freopen (file ".in", "r", stdin); \
    freopen (file ".out", "w", stdout);

using namespace std;

template<typename Tp>
inline void chmin (Tp &x, const Tp &y) { if (y < x) x = y; }
template<typename Tp>
inline void chmax (Tp &x, const Tp &y) { if (x < y) x = y; }

typedef double dbl;
typedef long long ll;
typedef long double ldb;

void init () {}

const int maxh = 4e1 + 2;
const int maxk = 18e0 + 2;
const int maxr = 2e2 + 20;
const ll mod = 1e9 + 7;
int k;
ll n, m, binom[maxk][maxk], dp[maxh][maxr][maxk];

void trans (int h, int pr, int nr, int pc, int nc, ll tk) {
    if (maxr <= nr || nr < 0) return;
    (dp[h][nr][nc] += dp[h + 1][pr][pc] * tk) %= mod;
}

void solve () {
    scanf ("%lld%lld%d", &n, &m, &k);
    binom[0][0] = 1ll;
    for (int i = 1; i <= k; ++i) {
        binom[i][0] = 1ll;
        for (int j = 1; j <= i; ++j) {
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
        }
    }
    dp[40][n >> 40][0] = 1ll;
    for (int i = 39; ~i; --i) {
        for (int pr = 0; pr < maxr; ++pr) {
            int nr = (pr << 1) | (n >> i & 1);
            for (int j = 0; j <= k; ++j) {
                for (int l = 0; l <= j; ++l) {
                    if (m >> i & 1) {
                        for (int c = 0, clim = k - j; c <= clim; ++c) {
                            trans (i, pr, nr - (k - l - c) * (l + c), j, j + (clim - c), binom[j][l] * binom[clim][c] % mod);
                        }
                    } else {
                        trans (i, pr, nr - (k - l) * l, j, j, binom[j][l]);
                    }
                }
            }
        }
        // for (int r = 0; r < maxr; ++r) {
        //     for (int j = 0; j <= k; ++j) {
        //         if (dp[i][r][j]) {
        //             fprintf (stderr, "%d %d %d %lld\n", i, r, j, dp[i][r][j]);
        //         }
        //     }
        // }
    }
    printf ("%lld\n", accumulate (dp[0][0], dp[0][0] + k + 1, 0ll) % mod);
}

int main () {
    // #ifndef LSY
    // FileIO_("");
    // #endif
    int t = 1; init ();
    // scanf ("%d", &t);
    while (t--) solve ();
    return 0;
}

// #ifdef LSY
// bool ed, debug = [] () {
//     static bool st; int memtyp = 0; dbl memsiz = &st - &ed;
//     static const string memstr[] = {"B", "KB", "MB", "GB"};
//     while (memsiz >= 1024.) { ++memtyp; memsiz /= 1024.; }
//     cerr << "Memory: " << memsiz << memstr[memtyp] << endl;
//     return atexit ([] () { cerr << "Time: " << 1000. *
// 		clock () / CLOCKS_PER_SEC << "ms" << endl; });
// } ();
// #endif