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: Accepted

Solution code:
mod = 10**9+7
n, K = map(int, input().split())
a = [[int(x) for x in input().split()] for _ in range(n)]

A = [a]

i = 1
while 2**i <= K:
    mtrix = []
    for j in range(n):
        raw = []
        for l in range(n):
            tmp = 0
            for k in range(n):
                tmp += A[-1][j][k] * A[-1][k][l]
            raw.append(tmp % mod)
        mtrix.append(raw)
    A.append(mtrix)
    i += 1

bit_max = i

ans = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            ans[i][j] = 1

for i in range(bit_max):
    if (K >> i) & 1:
        mtrix = []
        for j in range(n):
            raw = []
            for l in range(n):
                tmp = 0
                for k in range(n):
                    tmp += ans[j][k] * A[i][k][l]
                raw.append(tmp % mod)
            mtrix.append(raw)
        ans = mtrix

ans = sum(map(lambda x: sum(x) % mod, ans))

print(ans % mod)

Submission status: Accepted

Solution code:
def mat_mul(A, B):
    C = [[0]*len(B[0]) for _ in range(len(A))]
    
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(A[0])):
                C[i][j] += A[i][k]*B[k][j]
                C[i][j] %= MOD
    
    return C

def mat_pow(A, n):
    res = [[0]*len(A) for _ in range(len(A))]
    
    for i in range(len(A)):
        res[i][i] = 1
    
    while n>0:
        if n&1:
            res = mat_mul(res, A)
        
        n >>= 1
        A = mat_mul(A, A)
    
    return res

N, K = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9+7
res = mat_pow(a, K)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def multi_mat(M1,M2,n,mod=10**9+7):
    ans=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                ans[i][j]=(ans[i][j]+M1[i][k]*M2[k][j])%mod
    return ans
def pow_mat(M,k,n,mod=10**9+7):
    ans=[[0]*n for _ in range(n)]
    for i in range(n):ans[i][i]=1
    while k:
        if k%2:ans=multi_mat(ans,M,n,mod)
        M=multi_mat(M,M,n,mod)
        k//=2
    return ans

def main():
    n,k=map(int,input().split())
    A=[[int(_) for _ in input().split()] for i in range(n)]
    mod=10**9+7
    Ax=pow_mat(A,k,n,mod)
    print(sum(sum(x)%mod for x in Ax)%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:

def matmul(mt1, mt2, n, modp):
    ans = [[0 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                ans[i][j] += mt1[i][k] * mt2[k][j]
                ans[i][j] %= modp
    return ans


def pow_matrix(mt, k, n, modp):
    ans = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        ans[i][i] = 1

    while k:
        if k % 2:
            ans = matmul(ans, mt, n, modp)
        mt = matmul(mt, mt, n, modp)
        k //= 2
    return ans


def submit():
    n, k = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    modp = 10 ** 9 + 7
    ak = pow_matrix(a, k, n, modp)
    
    ans = 0
    for ar in ak:
        for ac in ar:
            ans += ac
            ans %= modp
    print(ans)

submit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

def resolve():
    n, p = map(int, input().split())
    
    base = [list(map(int, input().split())) for _ in range(n)]
    dp = [[(i == j) + 0 for j in range(n)] for i in range(n)]
    while p:
        if p & 1:
            dp = [[sum(dp[i][k] * base[k][j] % MOD for k in range(n)) % MOD for j in range(n)] for i in range(n)]
        base = [[sum(base[i][k] * base[k][j] % MOD for k in range(n)) % MOD for j in range(n)] for i in range(n)]
        p >>= 1

    print(sum(dp[i][j] for i in range(n) for j in range(n)) % MOD)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

def resolve():
    n, p = map(int, input().split())
    
    base = [list(map(int, input().split())) for _ in range(n)]
    dp = [[(i == j) + 0 for j in range(n)] for i in range(n)]
    while p:
        if p & 1:
            dp = [[sum(dp[i][k] * base[k][j] for k in range(n)) % MOD for j in range(n)] for i in range(n)]
        base = [[sum(base[i][k] * base[k][j] for k in range(n)) % MOD for j in range(n)] for i in range(n)]
        p >>= 1

    print(sum(dp[i][j] for i in range(n) for j in range(n)) % MOD)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n,k = map(int,input().split())
x = [list(map(int,input().split())) for i in range(n)]
ans = [[0]*i +[1]+[0]*(n-i-1) for i in range(n)]

def dot(A,B):
    res = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                res[i][j] += A[i][k]*B[k][j]
                res[i][j] %= mod
    return res

while k > 0:
    if k&1:
        ans = dot(ans, x)
    k = k >> 1
    x = dot(x,x)
res = 0
for i in range(n):
    for j in range(n):
        res += ans[i][j]
        res %= mod
print(res)

Submission status: Accepted

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


def matpow(A, x):
    if x == 1:
        return A % mod
    elif x % 2 == 0:
        return matpow(np.linalg.matrix_power(A, 2) % mod, x // 2)
    else:
        ans = matpow(np.linalg.matrix_power(A, 2) % mod, x // 2)
        ans = ans.dot(A) % mod
        return ans


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

A = np.array(A, dtype=object)
print(np.sum(matpow(A, K) % mod) % mod)

Submission status: Accepted

Solution code:
#少なくとも表示が楽
#import numpy as np


P=10**9+7
N,K=map(int,input().split())
G=[]
for index in range(N):
    G.append(list(map(int,input().split())))
#こうするしかない
#G=np.matrix(G)

#print(np.dot(G,G))
#print(G*G)は正しくならないがおそらくversionの問題

def mul(x,y,p): #x[0]とlen(y)が同じなのは前提
    res=[[0]*(len(y[0])) for _ in range(len(x))]
    #res[index1][index2]を決定
    for index1 in range(len(x)):
        for index2 in range(len(y[0])):
            for index3 in range(len(y)):  #len(x[0])でも良い　
                res[index1][index2]=(res[index1][index2]+x[index1][index3]*y[index3][index2])%p
    return res


def pow(x,y,p):
    res=[[0]*(len(x)) for _ in range(len(x))]
    for index1 in range(len(x)):
        res[index1][index1]=1
    
    while y>0:
        if y&1==1:
            res=mul(res,x,p)
        x=mul(x,x,p)
        y=y>>1
    
    return res

#print(np.matrix(pow(G,2,P)))

#DP_K=np.matrix(pow(G,K,P))
DP_K=pow(G,K,P)

ans=0
for i in range(N):
    for j in range(N):
        #ans=(ans+DP_K[i,j])%P
        ans=(ans+DP_K[i][j])%P

print(ans)

Submission status: Accepted

Solution code:
def product(A, B):
    C = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            C[i][j] = sum([A[i][k]*B[k][j] for k in range(n)]) % p
    return C

def matpow(A, k):
    if k == 1:
        return A
    if k % 2 == 0:
        B = matpow(A, k//2)
        return product(B, B)
    return product(A, matpow(A, k-1))

n, k = map(int, input().split())
p = 10**9+7
A = [list(map(int, input().split())) for i in range(n)]
B = matpow(A, k)
print(sum([sum(B[i]) for i in range(n)]) % p)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def matmul(a, b, mod):
    N0 = len(a)
    N1 = len(b[0])
    N2 = len(a[0])
    res = [[0] * N1 for _ in range(N0)]
    for i in range(N0):
        for j in range(N1):
            tmp = 0
            for k in range(N2):
                tmp = (tmp + a[i][k] * b[k][j]) % mod
            res[i][j] = tmp
    return res


def matpow(a, k, mod):
    N = len(a)
    res = [[0] * N for _ in range(N)]
    for i in range(N):
        res[i][i] = 1
    while k:
        if k & 1:
            res = matmul(res, a, mod)
        a = matmul(a, a, mod)
        k >>= 1
    return res


def solve():
    N, K = map(int, rl().split())
    a = [list(map(int, rl().split())) for _ in range(N)]
    MOD = 10 ** 9 + 7
    
    a = list(map(list, zip(*a)))
    mat = matpow(a, K, MOD)
    ans = 0
    for i in range(N):
        for j in range(N):
            ans = (ans + mat[i][j]) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np
mod=10**9+7
def solve():
    n,k = map(int,input().split())
    a = np.array([list(map(int,input().split())) for i in range(n)],dtype=np.int64)
    print(modpow(a,k).sum()%mod)
def mult(A,B):
    N=len(A)
    C = np.zeros((N,N),np.int64)
    for n in range(N):
        C[n] = (A[n,:][:,None] * B % mod).sum(axis=0) % mod
    return C
def modpow(A,k):
    n=len(A)
    res=np.eye(n,dtype=np.int64)
    for i in range(k.bit_length()):
        if k>>i&1:
            res=mult(A,res)
        A=mult(A,A)
    return res
solve()

Submission status: Accepted

Solution code:
# dp[n][i][j]=(頂点iから頂点jへ行く長さnのパスの個数)
# dp[n][i][j]=sum(dp[n-1][i][k]*a[k][j])⇒DP[n]=DP[n-1]*A DP[0]=Eより DP[n]=A^n
import sys
input = sys.stdin.readline

def dot(A,B,MOD=1000000007):
    N,M,L = len(A),len(A[0]),len(B[0])
    res = [[0]*L for i in range(N)]
    for i in range(N):
        for j in range(L):
            s = 0
            for k in range(M):
                s = (s + A[i][k]*B[k][j]) % MOD
            res[i][j] = s
    return res

def matPow(A,x,MOD=1000000007):
    N = len(A)
    res = [[0]*N for i in range(N)]
    for i in range(N):
        res[i][i] = 1
    for i in range(x.bit_length()):
        if (x>>i) & 1:
            res = dot(res,A)
        A = dot(A,A)
    return res

def main():
    n,k = map(int,input().split())
    mod = 10**9+7
    a = [list(map(int,input().split())) for i in range(n)]
    dp = matPow(a,k)
    ans = 0
    for i in range(n):
        for j in range(n):
            ans += dp[i][j]
    print(ans%mod)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    a=[[]for _ in range(N)]
    for i in range(N):
        a[i]=LI()
        
    def matDot(A,B,MOD):
        N,M,L = len(A),len(A[0]),len(B[0])
        
        res = [[0]*L for i in range(N)]

        for i in range(N):
            for j in range(L):
                s = 0
                for k in range(M):
                    s = (s + A[i][k]*B[k][j]) % MOD
                res[i][j] = s
        
        return res

    def matPow(A,x,MOD):
        N = len(A)
        res = [[0]*N for i in range(N)]
        
        for i in range(N):
            res[i][i] = 1
        
        for i in range(x.bit_length()):
            if (x>>i) & 1:
                res = matDot(res,A,MOD)
            A = matDot(A,A,MOD)
    
        return res
    
    to=matPow(a,K,mod)
    ans=0
    for i in range(N):
        for j in range(N):
            ans=(ans+to[i][j])%mod
    print(ans)
    
        

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    a=[[]for _ in range(N)]
    for i in range(N):
        a[i]=LI()
    
    adj=[[]for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if a[i][j]==1:
                adj[i].append(j)
    
        
    M=1
    mm=1
    for i in range(70):
        mm*=2
        M+=1
        if mm>=K:
            break
    
    dab=[[[0]*N for _ in range(N)]for i in range(M)]
    #ダブリング，M回，1~Nの各頂点をスタートして，1~Nそれぞれを終点とする通り数を記憶
    for j in range(N):
        for kk in range(len(adj[j])):
            k=adj[j][kk]
            dab[0][j][k]=1
    
    for i in range(M-1):
        for j in range(N):
            for k in range(N):
                cnt=dab[i][j][k]
                for l in range(N):
                    dab[i+1][j][l]+=cnt*dab[i][k][l]
                    dab[i+1][j][l]%=mod
                    
    ans=[1]*N
    for mm in range(M):#ダブリング
        if K>>mm&1:
            temp=[0]*N
            for i in range(N):#iにいるところから行けるところを探す．
                cnt=ans[i]
                for j in range(N):
                    temp[j]+=dab[mm][i][j]*cnt
                    
            for i in range(N):
                ans[i]=temp[i]
                
    res=0
    for i in range(N):
        res+=ans[i]
        res%=mod
    print(res)
        

main()

Submission status: Accepted

Solution code:
def matmul(p,q):
  c = [[0 for i in range(n)] for j in range(n)]
  for i in range(n):
    for j in range(n):
      for l in range(n):
        c[i][j] += p[i][l]*q[l][j]
        c[i][j] %= mod
  return c
n,k = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
als = [a]
for i in range(100):
  alsnxt = matmul(als[-1],als[-1])
  als.append(alsnxt)
ansmat = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
  ansmat[i][i] = 1
for i in range(100):
  if k&1<<i:
    ansmat = matmul(ansmat,als[i])
ans = 0
for i in range(n):
  for j in range(n):
    ans += ansmat[i][j]
    ans %= mod
print(ans)

Submission status: Accepted

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

mod=10**9+7

dp=[[[0 for i in range(0,N)] for j in range(0,N)] for k in range(0,62)]

for j in range(0,N):
    for k in range(0,N):
        dp[0][j][k]=A[j][k]

for i in range(1,62):
    for j in range(0,N):
        for k in range(0,N):
            dp[i][j][k]=sum(dp[i-1][j][l]*dp[i-1][l][k] for l in range(0,N))%mod

ans=[[[0 for i in range(0,N)] for j in range(0,N)] for k in range(0,63)]

for i in range(0,N):
    ans[0][i][i]=1

for k in range(0,62):
    if K>>k & 1==1:
        for i in range(0,N):
            for j in range(0,N):
                ans[k+1][i][j]=sum(dp[k][i][l]*ans[k][l][j] for l in range(0,N))%mod

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

print(sum(ans[62][i][j] for i in range(0,N) for j in range(0,N))%mod)

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

a = np.matrix(a, dtype=object)
ans = np.matrix(np.diag([1]*N), dtype=object)

while K:
    K, m = divmod(K, 2)
    if m:
        ans = ans * a
        ans = np.mod(ans, MOD)
    a = a*a
    a = np.mod(a, MOD)

print(ans.sum() % MOD)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
mod = 10 ** 9 + 7

a = [[int(i) for i in input().split()]for _ in range(n)]
b = [[0] * n for _ in range(n)]
for i in range(n):
    b[i][i] = 1


def mul(a, b):
    c = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            s = 0
            for k in range(n):
                s += a[i][k] * b[k][j]
                s %= mod
            c[i][j] = s
    return c


while k != 0:
    if k & 1 == 1:
        b = mul(b, a)
    a = mul(a, a)
    k //= 2

ans = sum(map(sum, b)) % mod

print(ans)

Submission status: Accepted

Solution code:
from numpy import*
(n,k),*a=[list(map(int,t.split()))for t in open(0)]
a=matrix(a,'O')
M=10**9+7
s=1
while k:s*=~k%2or a;k//=2;a=a*a%M
print(sum(s)%M)

Submission status: Accepted

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

def main():
    N,K = map(int,input().split())
    MOD = 10**9+7
    
    a = [list(map(int,input().split())) for _ in range(N)]
    arr = np.array(a,dtype=object)

    use = np.eye(N,dtype=object)
    while K>0:
        if K&1:
            use = np.dot(use,arr)%MOD
        arr = np.dot(arr,arr)%MOD
        K //= 2

    print(np.sum(use)%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

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), dtype=object)
	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=object)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
d = [list(map(int, input().split())) for _ in range(N)]
ln = K.bit_length()

def ArrayMultiple(a, b, mod):
  n = len(a)
  c = [[0] * n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        c[i][j] += a[i][k] * b[k][j]
        c[i][j] %= mod
  return c

bn = list(bin(K)[2: ])
bn.reverse()
res = [[int(i == x) for i in range(N)] for x in range(N)]
for i in range(ln):
  if int(bn[i]):
    res = ArrayMultiple(res, d, mod)
  d = ArrayMultiple(d, d, mod)
rres = 0
for r in res:
  for x in r:
    rres += x
    rres %= mod
print(rres)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def matDot(A,B,MOD):
    N,M,L = len(A),len(A[0]),len(B[0])
    
    res = [[0]*L for i in range(N)]

    for i in range(N):
        for j in range(L):
            s = 0
            for k in range(M):
                s = (s + A[i][k]*B[k][j]) % MOD
            res[i][j] = s
    
    return res

def matPow(A,x,MOD):
    N = len(A)
    res = [[0]*N for i in range(N)]
    
    for i in range(N):
        res[i][i] = 1
    
    for i in range(x.bit_length()):
        if (x>>i) & 1:
            res = matDot(res,A,MOD)
        A = matDot(A,A,MOD)
    
    return res

def main():
    n,k = map(int,input().split())
    mod = 10**9+7

    a = []
    for i in range(n):
        a.append(list(map(int,input().split())))

    b = matPow(a,k,mod)

    ans = 0
    for i in range(n):
        for j in range(n):
            ans = (ans+b[i][j])%mod

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def matDot(A,B,MOD):
    N,M,L = len(A),len(A[0]),len(B[0])
    
    res = [[0]*L for i in range(N)]

    for i in range(N):
        for j in range(L):
            s = 0
            for k in range(M):
                s = (s + A[i][k]*B[k][j]) % MOD
            res[i][j] = s
    
    return res

def matPow(A,x,MOD):
    N = len(A)
    res = [[0]*N for i in range(N)]
    
    for i in range(N):
        res[i][i] = 1
    
    for i in range(x.bit_length()):
        if (x>>i) & 1:
            res = matDot(res,A,MOD)
        A = matDot(A,A,MOD)
    
    return res

n,k = map(int,input().split())
mod = 10**9+7

a = []
for i in range(n):
    a.append(tuple(map(int,input().split())))

b = matPow(a,k,mod)

ans = 0
for i in range(n):
    for j in range(n):
        ans = (ans+b[i][j])%mod

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def matDot(A,B,MOD):
    N,M,L = len(A),len(A[0]),len(B[0])
    
    res = [[0]*L for i in range(N)]

    for i in range(N):
        for j in range(L):
            s = 0
            for k in range(M):
                s = (s + A[i][k]*B[k][j]) % MOD
            res[i][j] = s
    
    return res

def matPow(A,x,MOD):
    N = len(A)
    res = [[0]*N for i in range(N)]
    
    for i in range(N):
        res[i][i] = 1
    
    for i in range(x.bit_length()):
        if (x>>i) & 1:
            res = matDot(res,A,MOD)
        A = matDot(A,A,MOD)
    
    return res

n,k = map(int,input().split())
mod = 10**9+7

a = []
for i in range(n):
    a.append(list(map(int,input().split())))

b = matPow(a,k,mod)

ans = 0
for i in range(n):
    for j in range(n):
        ans = (ans+b[i][j])%mod

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def matDot(A,B,MOD):
    N,M,L = len(A),len(A[0]),len(B[0])
    
    res = [[0]*L for i in range(N)]

    for i in range(N):
        for j in range(L):
            s = 0
            for k in range(M):
                s = (s + A[i][k]*B[k][j]) % MOD
            res[i][j] = s
    
    return res

def matPow(A,x,MOD):
    N = len(A)
    res = [[0]*N for i in range(N)]
    
    for i in range(N):
        res[i][i] = 1
    
    for i in range(x.bit_length()):
        if (x>>i) & 1:
            res = matDot(res,A,MOD)
        A = matDot(A,A,MOD)
    
    return res

n,k = map(int,input().split())
mod = 10**9+7

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

b = matPow(a,k,mod)

ans = 0
for i in range(n):
    for j in range(n):
        ans = (ans+b[i][j])%mod

print(ans)

Submission status: Accepted

Solution code:
def matDot(A,B,MOD):
    N,M,L = len(A),len(A[0]),len(B[0])
    
    res = [[0]*L for i in range(N)]

    for i in range(N):
        for j in range(L):
            s = 0
            for k in range(M):
                s = (s + A[i][k]*B[k][j]) % MOD
            res[i][j] = s
    
    return res

def matPow(A,x,MOD):
    N = len(A)
    res = [[0]*N for i in range(N)]
    
    for i in range(N):
        res[i][i] = 1
    
    for i in range(x.bit_length()):
        if (2**i) & x:
            res = matDot(res,A,MOD)
        A = matDot(A,A,MOD)
    
    return res

n,k = map(int,input().split())
mod = 10**9+7

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

b = matPow(a,k,mod)

ans = 0
for i in range(n):
    for j in range(n):
        ans = (ans+b[i][j])%mod

print(ans)

Submission status: Accepted

Solution code:
def matDot(A,B,MOD):
    N,M,L = len(A),len(A[0]),len(B[0])
    
    res = [[0]*L for i in range(N)]

    for i in range(N):
        for j in range(L):
            s = 0
            for k in range(M):
                s = (s + A[i][k]*B[k][j]) % MOD
            res[i][j] = s
    
    return res

def matPow(A,x,MOD):
    N = len(A)
    res = [[0]*N for i in range(N)]
    
    for i in range(N):
        res[i][i] = 1
    
    for i in range(x.bit_length()):
        if (x>>i) & 1:
            res = matDot(res,A,MOD)
        A = matDot(A,A,MOD)
    
    return res

n,k = map(int,input().split())
mod = 10**9+7

a = [list(map(int,input().split())) for i in range(n)]
a = list(map(list, zip(*a)))

b = matPow(a,k,mod)

ans = 0
for i in range(n):
    for j in range(n):
        ans = (ans+b[i][j])%mod

print(ans)

Submission status: Accepted

Solution code:
def matDot(A,B,MOD):
    N,M,L = len(A),len(A[0]),len(B[0])
    
    res = [[0]*L for i in range(N)]

    for i in range(N):
        for j in range(L):
            s = 0
            for k in range(M):
                s = (s + A[i][k]*B[k][j]) % MOD
            res[i][j] = s
    
    return res

def matPow(A,x,MOD):
    N = len(A)
    res = [[0]*N for i in range(N)]
    
    for i in range(N):
        res[i][i] = 1
    
    for i in range(x.bit_length()):
        if (x>>i) & 1:
            res = matDot(res,A,MOD)
        A = matDot(A,A,MOD)
    
    return res

n,k = map(int,input().split())
mod = 10**9+7

a = [list(map(int,input().split())) for i in range(n)]
b = matPow(a,k,mod)

ans = 0
for i in range(n):
    for j in range(n):
        ans = (ans+b[i][j])%mod

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,k = map(int, input().split())
mod = 10**9 + 7
_a = [list(map(int, input().split())) for _ in range(n)]
a = np.array(_a, dtype = object)
e = np.eye(n, dtype = object)
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: Accepted

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

MOD = 10**9+7

def dot(A, B):
    N = len(A)
    K = len(A[0])
    assert len(B) == K
    M = len(B[0])
    C = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            C[i][j] = sum(A[i][k] * B[k][j] for k in range(K)) % MOD
    return C



def mp(A, n):
    assert len(A) == len(A[0])
    B = [[0] * len(A) for _ in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1

    while n:
        n, i = divmod(n, 2)
        if i:
            B = dot(A, B)
        A = dot(A, A)

    return B


ans = sum([sum(r) % MOD for r in mp(A, K)]) % MOD
print(ans)

Submission status: Accepted

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)
#
# v = a
# for _ in range(k - 1):
#     v = (v @ a) % M
# print(v.sum() % M)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def matmul(a, b, mod):
    m = len(a)
    l = len(a[0])
    n = len(b[0])
    ret = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            e = 0
            for k in range(l):
                e = (e + a[i][k] * b[k][j]) % mod
            ret[i][j] = e
    return ret

mod = 10**9+7
N, K = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
ans = [[i == j for j in range(N)] for i in range(N)]
while K > 0:
    if K & 1 == 1:
        ans = matmul(ans, a, mod)
    a = matmul(a, a, mod)
    K >>= 1
print(sum(sum(row) % mod for row in ans) % mod)

Submission status: Accepted

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, dtype=object)
p = 10**9 + 7

def mat_pow(a, n, mod):
    res = np.eye(len(a), dtype=object)
    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)
"""
ans = 0
for i in range(n):
    for j in range(n):
        ans += ak[i, j]
        ans %= p

print(ans)
"""

Submission status: Accepted

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, dtype=object)
p = 10**9 + 7

def mat_pow(a, n, mod):
    res = np.eye(len(a), dtype=object)
    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: Accepted

Solution code:
def Mmul(a, b):  # 行列の積
    # [ｍ×ｎ型][ｎ×ｐ型]
    m = len(a)
    n = len(a[0])
    if len(b) != n:
        raise ValueError('列と行の数が一致しません')
    p = len(b[0])
    ans = [[0]*p for _ in range(m)]
    for i in range(m):
        for j in range(p):
            for k in range(n):
                ans[i][j] += a[i][k]*b[k][j] % MOD
    return ans


def Mfactorial(n, p):  # n^p 繰り返し二乗法+行列の積
    if (p == 1):
        return n
    if (p % 2 == 0):
        t = Mfactorial(n, p // 2)
        return Mmul(t, t)
    return Mmul(Mfactorial(n, p - 1), n)


n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
MOD = 10**9+7
print(sum([sum(i) % MOD for i in Mfactorial(a, k)]) % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
def calc(A,B):
  res = [[0]*n for i in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] += A[i][k] * B[k][j]
      res[i][j] %= mod
  return res


def power(A,k):
  if k == 1:
    return A
  elif k % 2 == 0:
    tmp = power(A,k//2)
    return calc(tmp,tmp)
  elif k % 2 == 1:
    return calc(A,power(A,k-1))

result = power(A,k)
print(sum(map(sum,result))%mod)