Submission #5033463


Source Code Expand

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

KK = 70
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 571 ms
Memory 51072 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 571 ms 51072 KB
01 AC 390 ms 45276 KB
02 AC 503 ms 47580 KB
03 AC 251 ms 42204 KB
04 AC 207 ms 41308 KB
90 AC 167 ms 38256 KB
91 AC 167 ms 38256 KB