Submission #3974057

Source Code Expand

MOD = 10**9 + 7
def mul(A, B):
    return [[sum(A[i][k] * B[k][j] for k in range(N)) % MOD for j in range(N)] for i in range(N)]

N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]

R = [[i==j for i in range(N)] for j in range(N)]
while K:
    if K & 1:
        R = mul(R, A)
    A = mul(A, A)
    K >>= 1
print(sum(sum(r) for r in R) % MOD)

Submission Info

Submission Time
Task R - Walk
User yaketake08
Language PyPy3 (2.4.0)
Score 100
Code Size 392 Byte
Status AC
Exec Time 1598 ms
Memory 73436 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 23
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 0_04, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17
Case Name Status Exec Time Memory
0_00 AC 162 ms 38384 KiB
0_01 AC 175 ms 38256 KiB
0_02 AC 164 ms 38256 KiB
0_03 AC 174 ms 38256 KiB
0_04 AC 224 ms 42352 KiB
1_00 AC 162 ms 38256 KiB
1_01 AC 164 ms 38256 KiB
1_02 AC 218 ms 42736 KiB
1_03 AC 505 ms 48220 KiB
1_04 AC 212 ms 42224 KiB
1_05 AC 1240 ms 64860 KiB
1_06 AC 221 ms 42224 KiB
1_07 AC 1598 ms 73436 KiB
1_08 AC 969 ms 60508 KiB
1_09 AC 1257 ms 64988 KiB
1_10 AC 1259 ms 66524 KiB
1_11 AC 1192 ms 64988 KiB
1_12 AC 1126 ms 64092 KiB
1_13 AC 1323 ms 67804 KiB
1_14 AC 1248 ms 66268 KiB
1_15 AC 1248 ms 66396 KiB
1_16 AC 1268 ms 67036 KiB
1_17 AC 1350 ms 67292 KiB