Submission #8557390

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
K, N = map(int, input().split())
P = 10**9+7
k = 70
KK = 1<<k
nu = lambda L: int("".join([bin(KK+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(2*K-1)]]
def mult(A, B):
    return li(st(nu(A) * nu(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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

k = 70
KK = 1<<k
nu = lambda L: int("".join([bin(KK+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(2*K-1)]]

def mult(A, B):
    return li(st(nu(A) * nu(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