Submission #5022612


Source Code Expand

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

KK = 80
def ltoi(L):
    ret = 0
    for i in range(len(L)):
        ret += L[i] << KK*i
    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 PyPy3 (2.4.0)
Score 8
Code Size 833 Byte
Status AC
Exec Time 561 ms
Memory 50012 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 561 ms 50012 KB
01 AC 384 ms 45788 KB
02 AC 540 ms 49756 KB
03 AC 254 ms 42204 KB
04 AC 204 ms 41196 KB
90 AC 170 ms 38256 KB
91 AC 161 ms 38256 KB