Problem:


Score : 100 points

Problem Statement

There is a simple directed graph G with N vertices, numbered 1, 2, \ldots, N.

For each i and j (1 \leq i, j \leq N), you are given an integer a_{i, j} that represents whether there is a directed edge from Vertex i to j.
If a_{i, j} = 1, there is a directed edge from Vertex i to j; if a_{i, j} = 0, there is not.

Find the number of different directed paths of length K in G, modulo 10^9 + 7.
We will also count a path that traverses the same edge multiple times.

Constraints

All values in input are integers.

1 \leq N \leq 50

1 \leq K \leq 10^{18}

a_{i, j} is 0 or 1.

a_{i, i} = 0

Input

Input is given from Standard Input in the following format:

N K
a_{1, 1} \ldots a_{1, N}
:
a_{N, 1} \ldots a_{N, N}

Output

Print the number of different directed paths of length K in G, modulo 10^9 + 7.

Sample Input 1

4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0

Sample Output 1

6

G is drawn in the figure below:

There are six directed paths of length 2:

1 → 2 → 3

1 → 2 → 4

2 → 3 → 4

2 → 4 → 1

3 → 4 → 1

4 → 1 → 2

Sample Input 2

3 3
0 1 0
1 0 1
0 0 0

Sample Output 2

3

G is drawn in the figure below:

There are three directed paths of length 3:

1 → 2 → 1 → 2

2 → 1 → 2 → 1

2 → 1 → 2 → 3

Sample Input 3

6 2
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 0

Sample Output 3

1

G is drawn in the figure below:

There is one directed path of length 2:

4 → 5 → 6

Sample Input 4

1 1
0

Sample Output 4

0

Sample Input 5

10 1000000000000000000
0 0 1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 1 0 0
0 1 0 0 0 1 0 1 0 1
1 1 1 0 1 1 0 1 1 0
0 1 1 1 0 1 0 1 1 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 0 0 1 0 1
1 0 0 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
1 0 1 1 1 0 1 1 1 0

Sample Output 5

957538352

Be sure to print the count modulo 10^9 + 7.



Sample input:
4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0


Sample output:
6

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
from pprint import pprint
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def matpow(A, n):  # 2分累乗
	B = np.identity(len(A), np.int64)
	while n > 0:
		if n & 1:
			B = B.dot(A)
			B %= mod
		A = A.dot(A)
		A %= mod
		n >>= 1
	return B

N, K = MAP()
a = np.array([LIST() for _ in range(N)], dtype=np.int64)

print(matpow(a, K).sum()%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

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

A = np.matrix([list(map(int, input().split())) for _ in range(N)], dtype = np.int64)

def mod_pow(matrix, n, mod): #行列累乗を求める
    # print (matrix)
    if n == 0:
        N = len(matrix[:,0])
        # print (N)
        return np.matrix(np.eye(N, dtype = np.int64))
    res = mod_pow(np.mod(matrix * matrix, MOD), n // 2, MOD)
    res = np.mod(res, MOD)
    if n % 2 == 1:
        res *= matrix
        res = np.mod(res, MOD)
    return res

matrix = mod_pow(A, K, MOD)
# print (matrix)

ans = 0
for i in range(N):
    for j in range(N):
        tmp = matrix[i, j]
        if tmp < 0:
            print (error)
        ans += tmp
        ans %= MOD

ans %= MOD
print (ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

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

A = np.matrix([list(map(int, input().split())) for _ in range(N)], dtype = np.int64)

def mod_pow(matrix, n, mod): #行列累乗を求める
    # print (matrix)
    if n == 0:
        N = len(matrix[:,0])
        # print (N)
        return np.matrix(np.eye(N, dtype = np.int64))
    res = mod_pow(np.mod(matrix * matrix, MOD), n // 2, MOD)
    res = np.mod(res, MOD)
    if n % 2 == 1:
        res *= matrix
        res = np.mod(res, MOD)
    return res

matrix = mod_pow(A, K, MOD)
# print (matrix)

ans = 0
for i in range(N):
    for j in range(N):
        ans += matrix[i, j]
        ans %= MOD

ans %= MOD
print (ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

A = np.matrix([list(map(int, input().split())) for _ in range(N)], dtype = np.int64)

def mod_pow(matrix, n, mod): #行列累乗を求める
    # print (matrix)
    if n == 0:
        N = len(matrix[:,0])
        # print (N)
        return np.matrix(np.eye(N, dtype = np.int64))
    res = mod_pow(np.mod(matrix * matrix, MOD), n // 2, MOD)
    res = np.mod(res, MOD)
    if n % 2 == 1:
        res *= matrix
        res = np.mod(res, MOD)
    return res

matrix = mod_pow(A, K, MOD)
# print (matrix)

ans = 0
for i in range(N):
    for j in range(N):
        ans += matrix[i, j]
        ans %= MOD

ans %= MOD
print (ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

A = np.matrix([list(map(int, input().split())) for _ in range(N)], dtype = np.int64)

def mod_pow(matrix, n, mod): #行列累乗を求める
    # print (matrix)
    if n == 0:
        N = len(matrix[:,0])
        # print (N)
        return np.matrix(np.eye(N, dtype = np.int64))
    res = mod_pow(np.mod(matrix * matrix, MOD), n // 2, MOD)
    res = np.mod(res, MOD)
    if n % 2 == 1:
        res *= matrix
        res = np.mod(res, MOD)
    return res

matrix = mod_pow(A, K, MOD)
# print (matrix)

ans = 0
for i in range(N):
    for j in range(N):
        ans += matrix[i, j]

ans %= MOD
print (ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(10**9)
INF = float('inf')
MOD = 10**9 +7

def main():
  N, K = map(int, readline().split())
  A = np.array(read().split(), np.int64).reshape(N,N)
  
  def pow_array(a,k):#行列aのk乗の計算
    ans = np.eye(N)
    while k:
      if k%2:
        ans = np.dot(ans%MOD, a%MOD)
      a = np.dot(a%MOD, a%MOD)
      k>>=1
    return ans%MOD
  
  anser = pow_array(A,K).astype('int64').sum()
  print(anser)
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int, input().split())
mod = 10**9 + 7
a = np.array([list(map(int, input().split())) for _ in range(n)], dtype = np.int64)
e = np.eye(n, dtype = np.int64)
while k:
  if k & 1:
    e = np.dot(e, a) % mod
  k >>= 1
  a = np.dot(a, a) % mod
print(e.sum() % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int, input().split())
mod = 10**9 + 7
a = np.array([list(map(int, input().split())) for _ in range(n)])
e = np.eye(n, dtype = int)
while k:
  if k & 1:
    e = np.dot(e, a) % mod
  k >>= 1
  a = np.dot(a, a) % mod
p = 0
for i in range(n):
  for j in range(n):
    p = (p + e[i][j]) % mod
print(p)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int, input().split())
mod = 10**9 + 7
a = np.array([list(map(int, input().split())) for _ in range(n)])
e = np.eye(n, dtype = int)
while k:
  if k & 1:
    e = np.dot(e, a) % mod
  k >>= 1
  a = np.dot(a, a) % mod
print(sum(sum(e) % mod)%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int, input().split())
mod = 10**9 + 7
a = np.array([list(map(int, input().split())) for _ in range(n)])
e = np.eye(n, dtype = np.int64)
while k:
  if k & 1:
    e = np.dot(e, a) % mod
  k >>= 1
  a = np.dot(a, a) % mod
print(e.sum() % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int, input().split())
mod = 10**9 + 7
a = np.array([list(map(int, input().split())) for _ in range(n)])
e = np.eye(n, dtype = np.int32)
while k:
  if k & 1:
    e = np.dot(e, a) % mod
  k >>= 1
  a = np.dot(a, a) % mod
print(e.sum() % mod)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)];

import numpy as np
n = 30
k = 100
np.random.seed(100)
a = np.random.randint(0, 2, size=(n, n))

graph = [[] for _ in range(n)]
for i, row in enumerate(a):
    for j, value in enumerate(row):
        if value:
            graph[i].append(j)

# dp = [[None] * (k + 1) for _ in range(n)]
# def dfs(i, at=k):
#     if dp[i][at] is not None:
#         return dp[i][at]
#     if at == 1:
#         r = len(graph[i])
#         dp[i][at] = r
#         return dp[i][at]
#
#     cnt = 0
#     for nxt in graph[i]:
#         cnt += dfs(nxt, at - 1)
#     dp[i][at] = cnt
#     return cnt
#
# print([dfs(i, at=k) for i in range(n)])
#
# for v in dp:
#     print(v)

# -------
import numpy as np
a = np.array(a, dtype=int)

M = 10**9 + 7
def powmod(a, n):
    if n == 0:
        return np.eye(np.alen(a), dtype=int)
    if n % 2:
        return (powmod(a, n - 1).dot(a)) % M
    r = powmod(a, n // 2)

    calc = []
    for row in r.T:
        calc.append(((row * r) % M).sum(axis=-1))
    return np.array(calc).T % M

print(powmod(a, k).sum() % M)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)];

# import numpy as np
# n = 50
# k = 10**15
# a = np.random.randint(0, 2, size=(n, n))

graph = [[] for _ in range(n)]
for i, row in enumerate(a):
    for j, value in enumerate(row):
        if value:
            graph[i].append(j)

# dp = [[None] * (k + 1) for _ in range(n)]
# def dfs(i, at=k):
#     if dp[i][at] is not None:
#         return dp[i][at]
#     if at == 1:
#         r = len(graph[i])
#         dp[i][at] = r
#         return dp[i][at]
#
#     cnt = 0
#     for nxt in graph[i]:
#         cnt += dfs(nxt, at - 1)
#     dp[i][at] = cnt
#     return cnt
#
# print([dfs(i, at=k) for i in range(n)])
#
# for v in dp:
#     print(v)

# -------
import numpy as np
a = np.array(a)

M = 10**9 + 7
def powmod(a, n):
    if n == 0:
        return np.eye(np.alen(a), dtype=int)
    if n % 2:
        return (powmod(a, n - 1).dot(a)) % M
    r = powmod(a, n // 2)
    return (r.dot(r)) % M

print(powmod(a, k).sum() % M)

# v = a
# for _ in range(k - 1):
#     v = v @ a
# print(v)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

mod = 10**9+7
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int64)
ans = np.identity(N, dtype=np.int64)
while K > 0:
    if K & 1 == 1:
        ans = np.dot(ans, a) % mod
    a = np.dot(a, a) % mod
    K >>= 1
print(np.sum(ans) % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
a = [list(map(int , input().split())) for _ in range(n)]
a = np.array(a, np.int64)
p = 10**9 + 7

def mat_pow(d, n, mod):
    a = d.copy()
    res = np.eye(len(a), dtype=np.int64)
    while(n > 0):
        if(n & 1 == 1):
            res = np.dot(res, a) % mod#res.dot(a) % mod
        a = np.dot(a, a) % mod#a.dot(a) % mod
        n = n >> 1
    return res
ak = mat_pow(a, k, p)
#print(ak % p)
#print(ak.sum() % p)
ans = 0
for i in range(n):
    for j in range(n):
        ans += ak[i, j]
        ans %= p

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
a = [list(map(int , input().split())) for _ in range(n)]
a = np.array(a, np.int64)
p = 10**9 + 7

def mat_pow(d, n, mod):
    a = d.copy()
    res = np.eye(len(a), dtype=np.int64)
    while(n > 0):
        if(n & 1 == 1):
            res = res.dot(a) % mod
        a = a.dot(a) % mod
        n = n >> 1
    return res
ak = mat_pow(a, k, p)
print(ak.sum() % p)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
a = [list(map(int , input().split())) for _ in range(n)]
a = np.array(a, np.int64)
p = 10**9 + 7

def mat_pow(d, n, mod):
    a = d.copy()
    res = np.eye(len(a), dtype=np.int64)
    while(n > 0):
        if(n & 1 == 1):
            res = res.dot(a) % mod
        a = a.dot(a) % mod
        n = n >> 1
    return res
ak = mat_pow(a, k, p)
print(sum(sum(ak)% p) % p)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
a = [list(map(int , input().split())) for _ in range(n)]
a = np.array(a, np.int64)
p = 10**9 + 7

def mat_pow(a, n, mod):
    res = np.eye(len(a), dtype=np.int64)
    while(n > 0):
        if(n & 1 == 1):
            res = res.dot(a) % mod
        a = a.dot(a) % mod
        n = n >> 1
    return res
ak = mat_pow(a, k, p)
print(sum(sum(ak)% p) % p)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
a = [list(map(int , input().split())) for _ in range(n)]
a = np.array(a, np.int64)
p = 10**9 + 7

def mat_pow(a, n):
    res = np.eye(a.shape[0], a.shape[1], dtype=np.int64)
    while(n > 0):
        if(n & 1 == 1):
            res = res.dot(a) % p
            #res = res * a % p
        a = a.dot(a) % p
        #a = a * a
        n = n >> 1 #ビットシフト
    return res

#print(mat_pow(2, 10-1), 2 **10)
ak = mat_pow(a, k)
#print(ak)
print(sum(sum(ak))%p)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
a = [list(map(int , input().split())) for _ in range(n)]
a = np.array(a, np.int64)
p = 10**9 + 7

def mat_pow(a, n):
    res = np.eye(a.shape[0], a.shape[1], dtype=np.int64)
    while(n > 0):
        if(n & 1 == 1):
            res = res.dot(a) % p
            #res = res * a % p
        a = a.dot(a) % p
        #a = a * a
        n = n >> 1 #ビットシフト
    return res

#print(mat_pow(2, 10-1), 2 **10)
ak = mat_pow(a, k)
#print(ak)
print(sum(sum(ak)%p)%p)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
a = [list(map(int , input().split())) for _ in range(n)]
a = np.array(a, np.int64)
p = 10**9 + 7

def mat_pow(a, n):
    res = a
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            res = res.dot(a) % p
            #res = res * a % p
        a = a.dot(a) % p
        #a = a * a
        n = n >> 1 #ビットシフト
    return res

#print(mat_pow(2, 10-1), 2 **10)
ak = mat_pow(a, k-1)
#print(ak)
print(sum(sum(ak)%p)%p)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.array([input().split() for i in range(N)], dtype=int)
MOD = 10**9 + 7

def power(A, k, mod=10**9+7):
  if k == 0:
    return np.eye(len(A), dtype=int)
  elif k == 1:
    return A
  elif k % 2 == 0:
    return power(np.dot(A, A)%mod, k//2)
  else:
    return np.dot(A, power(A, k-1))%mod
  

trans = power(A, K)  
print(np.sum(trans)%MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.array([list(map(int, input().split())) for i in range(N)])
MOD = 10**9 + 7

dp = np.eye(N, dtype=int)

def power(A, k, mod=10**9+7):
  if k == 0:
    return np.eye(len(A), dtype=int)
  elif k == 1:
    return A
  elif k % 2 == 0:
    return power(np.dot(A, A)%MOD, k//2)
  else:
    return np.dot(A, power(np.dot(A, A)%MOD, k//2))%MOD
  

trans = power(A, K)  
print(np.sum(np.dot(dp, trans)%MOD)%MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    mod=10**9+7
    n,k=map(int,input().split())
    A=np.matrix([list(map(int,input().split()))for _ in range(n)],dtype=np.uint64)
    D=A.copy()
    for i in range(k.bit_length()-1,0,-1):
        D=(D*D)%mod
        if k&1<<(i-1)>0:
            D=(D*A)%mod
    print(int(((D*np.ones(n,dtype=np.uint64)[:,np.newaxis])%mod).sum()%mod))
main()

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    mod=10**9+7
    n,k=map(int,input().split())
    A=np.matrix([list(map(int,input().split()))for _ in range(n)],dtype=np.int64)
    D=A.copy()
    for i in range(k.bit_length()-1,0,-1):
        D=(D*D)%mod
        if k&1<<(i-1)>0:
            D=(D*A)%mod
    print(((D*np.ones(n,dtype=np.int64)[:,np.newaxis])%mod).sum()%mod)
main()

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    mod=10**9+7
    n,k=map(int,input().split())
    A=np.matrix([list(map(int,input().split()))for _ in range(n)],dtype=np.int64)
    D=A.copy()
    for i in range(k.bit_length()-1,0,-1):
        D=(D*D)%mod
        if k&1<<(i-1)>0:
            D=(D*A)%mod
    print((D*np.ones(n,dtype=np.int64)[:,np.newaxis]).sum()%mod)
main()

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10**9 +7

n, k = map(int, input().split())
a = [list(map(int, input().split()))  for _ in range(n)]

a = np.array(a , dtype= 'int64')
x = np.ones(n, dtype= 'int64')

k_bin = str(bin(k))[2:]
k_len = len(k_bin)

a_2 = [0]* k_len
a_2[0] = a

for i in range(1,k_len):
    a_2[i] = np.linalg.matrix_power(a_2[i-1],2) % mod

a_k = np.identity(n, dtype='int64')
for i in range(k_len):
    if( k_bin[k_len-i-1] == '1'):
        a_k = np.dot(a_k, a_2[i]) % mod

x = np.dot(x, a_k)

print(int(sum(x)) % mod)

Submission status: Wrong Answer

Solution code:
from numpy import*
N,K,*A=map(int,open(0).read().split())
X=matrix(A,"O").reshape(N,N)
M=10**9+7
S=2
while K:S*=~K%2or X;K//=2;X=X*X%M
print(sum(S)%M)

Submission status: Wrong Answer

Solution code:
from numpy import*
M=10**9+7
m=lambda*z:map(int,raw_input().split())
n,k=m()
b=[1]*n
a=matrix(map(m,b))
while k:b*=[1,a][k&1];a=a*a%M;k/=2
print sum(b)%M

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, input().split())
M = 10**9+7
xs = []
for _ in range(N):
    xs.append(list(map(int, input().split())))
X = np.array(xs, dtype="uint64")
S = np.ones(N, dtype="uint64")
#Xs = [X]
for _ in range(60):
#    Xs.append(np.dot(Xs[-1],Xs[-1])%M)
    if K%2:
        S = np.dot(X, S)%M
    K = K//2
    X = np.dot(X, X)%M
S = np.array(S, dtype="int64")
r = 0
for s in S:
    r = (r + s)%M
print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, input().split())
M = 10**9+7
xs = []
for _ in range(N):
    xs.append(list(map(int, input().split())))
X = np.array(xs, dtype="int64")
S = np.ones(N, dtype="int64")
#Xs = [X]
for _ in range(60):
#    Xs.append(np.dot(Xs[-1],Xs[-1])%M)
    if K%2:
        S = np.dot(X, S)%M
    K = K//2
    X = np.dot(X, X)%M
r = 0
for s in S:
    r = (r + s)%M
print(r)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(N)]

mod = 10**9+7

import numpy as np

a = np.array(A)
Mat = np.eye(N)
print(Mat)
while K:
    if K%2:
        Mat = np.dot(Mat, a)%mod
    a = np.dot(a, a)%mod
    K //= 2
    
ans = 0
for i in range(N):
    for j in range(N):
        ans += int(Mat[i, j])
        ans %= mod
        
print(ans,a)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(N)]

mod = 10**9+7

import numpy as np

a = np.array(A)
L = [[0]*N for _ in range(N)]
for i in range(N):
    L[i][i] = 1
Mat = np.array(L)

while K:
    if K%2:
        Mat = np.dot(Mat, a)%mod
    a = np.dot(a, a)%mod
    K //= 2
    
ans = 0
for i in range(N):
    for j in range(N):
        ans += Mat[i, j]
        ans %= mod
        
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(N)]

mod = 10**9+7

import numpy as np

a = np.array(A)
L = [[0]*N for _ in range(N)]
for i in range(N):
    L[i][i] = 1
I = np.array(L)

def matrixpow(a, n, mod):
    if n == 0:
        return I
    elif n%2 == 0:
        return matrixpow(np.dot(a, a)%mod, n//2, mod)%mod
    else:
        return np.dot(a, matrixpow(np.dot(a, a)%mod, (n-1)//2, mod))%mod
    
Mat = matrixpow(a, K, mod)
ans = 0
for i in range(N):
    for j in range(N):
        ans += Mat[i, j]
        ans %= mod
        
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(N)]

mod = 10**9+7

import numpy as np

a = np.array(A)
L = [[0]*N for _ in range(N)]
for i in range(N):
    L[i][i] = 1
I = np.array(L)

def matrixpow(a, n, mod):
    if n == 0:
        return I
    elif n%2 == 0:
        return matrixpow(np.dot(a, a)%mod, n//2, mod)%mod
    else:
        return np.dot(a, matrixpow(np.dot(a, a)%mod, (n-1)//2, mod))%mod
    
Mat = matrixpow(a, K, mod)
ans = np.sum(Mat)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(N)]

mod = 10**9+7

import numpy as np

A = np.array(A)
L = [[0]*N for _ in range(N)]
for i in range(N):
    L[i][i] = 1
I = np.array(L)

def matrixpow(a, n, mod):
    if n == 0:
        return I
    elif n == 1:
        return a
    elif n%2 == 0:
        return matrixpow(np.dot(a, a)%mod, n//2, mod)
    else:
        return np.dot(a, matrixpow(np.dot(a, a)%mod, (n-1)//2, mod))%mod
    
Mat = matrixpow(A, K, mod)
ans = np.sum(Mat)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(N)]

mod = 10**9+7

import numpy as np

A = np.array(A)
L = [[0]*N for _ in range(N)]
for i in range(N):
    L[i][i] = 1
I = np.array(L)

def matrixpow(a, n, mod):
    if n == 0:
        return I
    elif n%2 == 0:
        return matrixpow(np.dot(a, a)%mod, n//2, mod)
    else:
        return np.dot(a, matrixpow(np.dot(a, a)%mod, (n-1)//2, mod))%mod
    
Mat = matrixpow(A, K, mod)
ans = np.sum(Mat)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
import numpy as np

MOD = 1000000007  # type: int


def solve(N: int, K: int, a: "List[List[int]]"):
    a = np.asarray(a, dtype=np.int64)
    ans = np.identity(N, dtype=np.int64)
    while K > 0:
        if K & 1:
            ans = np.mod(np.dot(ans, a), MOD)
        a = np.mod(np.dot(a, a), MOD)
        K >>= 1
    print(ans.sum() % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [[int(next(tokens)) for _ in range(N)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, K, a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    N, K = map(int, input().split())
    mod = np.int64(10 ** 9 + 7)
    A = [[int(x) for x in input().split()] for _ in range(N)]
    A = np.asarray(A, dtype=np.int64)
    ans = np.identity(N, dtype=np.int64)
    while K > 0:
        if K & 1:
            ans = np.mod(np.dot(ans, A), mod)
        A = np.mod(np.dot(A, A), mod)
        K >>= 1
    print(np.mod(ans.sum(), mod))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    N, K = map(int, input().split())
    mod = 10 ** 9 + 7
    A = [[int(x) for x in input().split()] for _ in range(N)]
    A = np.asarray(A, dtype=np.int64)
    ans = np.identity(N, dtype=np.int64)
    while K > 0:
        if K & 1:
            ans = np.mod(np.dot(ans, A), mod)
        A = np.mod(np.dot(A, A), mod)
        K >>= 1
    print(ans.sum() % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

mod = 10**9+7
A = np.matrix(A)
I = [[0]*N for _ in range(N)]
for i in range(N):
    I[i][i] = 1
    
def P(a, x):
    if x == 0:
        return I
    if x == 1:
        return a%mod
    if x%2 == 0:
        return P((a**2)%mod, x//2)
    else:
        return a*P((a**2)%mod, (x-1)//2)%mod

L = P(A, K)
ans = 0
for i in range(N):
    for j in range(N):
        ans += L[i, j]
        ans %= mod
        
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

mod = 10**9+7
A = np.matrix(A)
L = [[0]*N for _ in range(N)]
for i in range(N):
    L[i][i] = 1
L = np.matrix(L)

for i in range(100):
    if K&(2**i) == 2**i:
        L = np.dot(L, A)
        L %= mod
    A = np.dot(A, A)
    A %= mod
    
ans = 0
for i in range(N):
    for j in range(N):
        ans += L[i, j]
        ans %= mod
        
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

mod = 10**9+7
A = np.matrix(A)
L = [[0]*N for _ in range(N)]
for i in range(N):
    L[i][i] = 1
L = np.matrix(L)

for i in range(70):
    if K&(2**i) == 2**i:
        L = np.dot(L, A)
        L %= mod
    A = np.dot(A, A)
    A %= mod
    
ans = 0
for i in range(N):
    for j in range(N):
        ans += L[i, j]
        ans %= mod
        
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = [[int(c) for c in input().split()] for _ in range(n)]
    can = np.array(can, 'O')

    answer = np.eye(n)
    while k:
        if k % 2:
            answer = np.dot(answer, can) % MOD
        can = np.dot(can, can) % MOD
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += answer[i, j]
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = [[int(c) for c in input().split()] for _ in range(n)]
    can = np.array(can)

    answer = np.eye(n)
    while k:
        if k % 2:
            answer = np.dot(answer, can) % MOD
        can = np.dot(can, can) % MOD
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += answer[i,j]
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = np.zeros((n,n), dtype=int)
    for i in range(n):
        for j, e in enumerate(int(c) for c in input().split()):
            can[i,j] = e

    answer = np.eye(n, dtype=int)
    while k:
        if k % 2:
            answer = np.dot(answer, can) % MOD
        can = np.dot(can, can) % MOD
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += answer[i,j]
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = np.zeros((n,n), dtype=np.ctypeslib.integer)
    for i in range(n):
        for j, e in enumerate(int(c) for c in input().split()):
            can[i,j] = e

    answer = np.eye(n, dtype=np.ctypeslib.integer)
    while k:
        if k % 2:
            answer = np.dot(answer, can)
        can = np.dot(can, can)
        k //= 2

    total = np.sum(answer) % MOD

    # for i in range(n):
    #     for j in range(n):
    #         total += answer[i,j]
    #         if total >= MOD:
    #             total -= MOD

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = np.zeros((n,n), dtype=np.int)
    for i in range(n):
        for j, e in enumerate(int(c) for c in input().split()):
            can[i,j] = e

    answer = np.identity(n, dtype=np.int)
    while k:
        if k % 2:
            answer = np.dot(answer, can)
        can = np.dot(can, can)
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += answer[i,j]
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10**9 + 7

N, K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
A = np.array(A, dtype=np.int64)
B = np.eye(N, dtype=np.int64)

while K > 0:
    if K & 1:
        B = np.dot(B, A) % mod
    A = np.dot(A, A) % mod
    K >>= 1

ans = B.sum() % mod
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10**9 + 7

N, K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
A = np.array(A, dtype='int64')
B = np.eye(N, dtype='int64')

while K > 0:
    if K & 1:
        B = np.dot(B, A) % mod
    A = np.dot(A, A) % mod
    K >>= 1

ans = B.sum() % mod
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10**9 + 7

N, K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
A = np.array(A)
B = np.eye(N, dtype=int)

while K > 0:
    if K & 1:
        B = np.dot(B, A) % mod
    A = np.dot(A, A) % mod
    K >>= 1

ans = B.sum() % mod
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10**9 + 7

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

ans = np.linalg.matrix_power(A, K).sum()
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n, k = MI()
    aa = LLI(n)
    aa = np.array(aa, dtype="i8")
    ans = np.eye(n, dtype="i8")
    while k:
        if k & 1:
            ans = np.dot(ans, aa)%md
        aa = np.dot(aa, aa)%md
        k >>= 1
    # print(ans)
    print(np.sum(ans) % md)

main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n, k = MI()
    aa = LLI(n)
    aa = np.array(aa, dtype="i8")
    ans = np.eye(n, dtype="i8")
    while k:
        if k & 1:
            ans = np.dot(ans, aa)
            ans %= md
        aa = np.dot(aa, aa)
        aa %= md
        k >>= 1
    # print(ans)
    print(np.sum(ans) % md)

main()