Submission #5410498

---

Source Code Expand

K, N = map(int, input().split())
P = 10**9+7

KK = 70
def ltoi(L):
    ret = 0
    for l in L[::-1]:
        ret <<= KK
        ret += l
    return ret
def itol(n):
    ret = []
    for i in range(2*K-1):
        ret.append((n>>i*KK) & ((1<<KK)-1))
    return ret

def mult(A, B):
    return itol(ltoi(A)*ltoi(B))
def prod(A, B):
    C = mult(A, B)
    for i in range(len(C)):
        C[i] %= P
    for i in range(K+1, 2*K-1)[::-1]:
        C[i-1] += 2*C[i]
        C[i-K-1] -= C[i]
        C[i-1] %= P
        C[i-K-1] %= P
        C[i] = 0
    for i in range(K):
        C[i] += C[K]
        C[i] %= P
    C[K] = 0
        
    return C[:K]
def poww(A, n):
    if n == 1: return A
    if n % 2 == 0: return poww(prod(A,A), n//2)
    return prod(A, poww(A, n-1))

print(sum(poww([0,1], N-1))%P)

Submission Info

Judge Result