rt，我觉得这么写不会溢出啊……

import numpy as np

def popcount(x): return bin(x).count('1')
P = int(1e9 + 7)
class matrix:
    def __init__(self, x): self.x = x
    def __matmul__(self, other): return matrix(np.array([[np.sum(self.x[i] @ other.x[:, j] % P) % P for j in range(other.x.shape[1])] for i in range(self.x.shape[0])]))

n, m, k = map(int, input().split())
b = matrix(np.zeros((1 << m, 1 << m), dtype=np.int64))

for i in range(1 << m):
    if popcount(i) > k: continue
    b.x[i >> 1][i] = 1
    j = (i >> 1) | (1 << (m - 1))
    if popcount(j) <= k:
        b.x[j][i] = 1

res = matrix(np.identity(1 << m, np.int64))
while n:
    if n & 1: res = res @ b
    b = b @ b
    n >>= 1

print(res.x.trace() % P)