Submission #19684390

---

Source Code Expand

mod = 10**9 + 7
def mat_dot(a, b):
    n = len(a)
    r = len(a[0])
    m = len(b[0])
    c = [[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(r):
                c[i][j] += a[i][k] * b[k][j]
                c[i][j] % mod
    return c
def mat_pow(a, n):
    m = len(a)
    b = [[1 if i == j else 0 for j in range(m)] for i in range(m)]
    while n > 0:
        if n & 1:
            b = mat_dot(b, a)
        a = mat_dot(a, a)
        n >>= 1
    return b
k, n =  map(int, input().split())
if n <= k:
    print(1)
    exit()
a = [[1 if i == 0 or i - 1 == j else 0 for j in range(k)] for i in range(k)]
a = mat_pow(a, n - k)
a = mat_dot(a, [[1] for i in range(k)])
print(a[0][0])

Submission Info

Judge Result