Submission #5410489


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

Submission Time
Task T - フィボナッチ
User Kiri8128
Language Python (3.4.3)
Score 8
Code Size 836 Byte
Status AC
Exec Time 615 ms
Memory 4072 KB

Judge Result

Set Name All
Score / Max Score 8 / 8
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 615 ms 4060 KB
01 AC 354 ms 3696 KB
02 AC 591 ms 4072 KB
03 AC 144 ms 3440 KB
04 AC 48 ms 3188 KB
90 AC 17 ms 3064 KB
91 AC 17 ms 3064 KB