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: Time Limit Exceeded

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

mod = 10**9+7
n, k = map(int, input().split())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
def matmul(X, Y):
  Z = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        Z[i][j] += X[i][k] * Y[k][j]
        Z[i][j] %= mod
  return Z
  
def matpow(k):
  if k == 1:
    return A
  if k%2:
    return matmul(A, matpow(k-1))
  X = matpow(k//2)
  return matmul(X, X)

B = matpow(k)
ans = 0
for i in range(n):
  for j in range(n):
    ans += B[i][j]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(N)]
a=np.array(a,dtype=np.int64)
MOD=10**9+7

def matmul(A,B,MOD):
    N=len(A)
    C=np.zeros((N,N),dtype=np.int64)

    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] =(C[i][j]+ A[i][k]*B[k][j])%MOD
    return C

def mat_power(A,k,MOD):
    N=len(A)
    D=np.identity(N,dtype=np.int64)
    while k:
        if k & 1:
            D=matmul(D,A,MOD)
        A = matmul(A,A,MOD)
        k >>= 1

    return D

A=mat_power(a,K,MOD)
ans=0
for i in range(N):
    for j in range(N):
        ans=(ans+A[i][j])%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7

def calc(mat1,mat2):
  n=len(mat1)
  ret=[[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        ret[i][j]+=mat1[i][k]*mat2[k][j]
        ret[i][j]%=mod
  return ret

n,k=map(int,input().split())
tmp=[[0]*n for _ in range(n)]
for i in range(n):
  tmp[i][i]=1
matrix=[list(map(int,input().split())) for _ in range(n)]
for i in range(60):
  if k&(1<<i):
    tmp=calc(tmp,matrix)
  matrix=calc(matrix,matrix)  
ans=0
for i in range(n):
  for j in range(n):
    ans+=tmp[i][j]
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def matrix_cal(A, B, mod):
    a, b = A.shape
    c, d = B.shape
    # print(a, b, c, d)
    assert(b == c)
    ans = np.zeros((a, d), dtype=np.int64)
    for aa in range(a):
        for dd in range(d):
            v = 0
            for bb in range(b):
                v = (v + A[aa][bb] * B[bb][dd]) % mod
            ans[aa][dd] = v
    return ans


def matrix_pow(A, n, mod=0):
    if n == 1:
        return A
    a = matrix_pow(A, n//2, mod)
    ans = matrix_cal(a, a, mod)
    if n % 2 == 1:
        ans = matrix_cal(ans, A, mod)
    return ans


N, K = na()
A = np.array(naa(N), dtype=np.int32)
mod = 10 ** 9 + 7

B = matrix_pow(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: Time Limit Exceeded

Solution code:
import sys
import numpy as np

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def matrix_cal(A, B, mod):
    a, b = A.shape
    c, d = B.shape
    # print(a, b, c, d)
    assert(b == c)
    ans = np.zeros((a, d), dtype=np.int64)
    for aa in range(a):
        for dd in range(d):
            v = 0
            for bb in range(b):
                v = (v + A[aa][bb] * B[bb][dd]) % mod
            ans[aa][dd] = v
    return ans


def matrix_pow(A, n, mod=0):
    if n == 1:
        return A
    a = matrix_pow(A, n//2, mod)
    ans = matrix_cal(a, a, mod)
    if n % 2 == 1:
        ans = matrix_cal(ans, A, mod)
    ans %= mod
    return ans


N, K = na()
A = np.array(naa(N), dtype=np.int64)
mod = 10 ** 9 + 7

B = matrix_pow(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: Time Limit Exceeded

Solution code:
class SquareMatrix():
    def __init__(self, n, mod=1000000007):
        self.n = n
        self.mat = [[0 for j in range(n)] for i in range(n)]
        self.mod = mod

    @staticmethod
    def id(n, mod=1000000007):
        res = SquareMatrix(n, mod)
        for i in range(n):
            res.mat[i][i] = 1
        return res

    @staticmethod
    def modinv(n, mod):
        assert n % mod != 0
        c0, c1 = n, mod
        a0, a1 = 1, 0
        b0, b1 = 0, 1
        while c1:
            a0, a1 = a1, a0 - c0 // c1 * a1
            b0, b1 = b1, b0 - c0 // c1 * b1
            c0, c1 = c1, c0 % c1
        return a0 % mod

    def set(self, arr):
        for i in range(self.n):
            for j in range(self.n):
                self.mat[i][j] = arr[i][j] % self.mod

    def operate(self, vec):
        assert len(vec) == self.n
        res = [0 for _ in range(self.n)]
        for i in range(self.n):
            for j in range(self.n):
                res[i] += self.mat[i][j] * vec[j]
                res[i] %= self.mod
        return res

    def add(self, other):
        assert other.n == self.n
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                res.mat[i][j] = self.mat[i][j] + other.mat[i][j]
                res.mat[i][j] %= self.mod
        return res

    def subtract(self, other):
        assert other.n == self.n
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                res.mat[i][j] = self.mat[i][j] - other.mat[i][j]
                res.mat[i][j] %= self.mod
        return res

    def times(self, k):
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                res.mat[i][j] = self.mat[i][j] * k
                res.mat[i][j] %= self.mod
        return res

    def multiply(self, other):
        assert self.n == other.n
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                for k in range(self.n):
                    res.mat[i][j] += self.mat[i][k] * other.mat[k][j]
                    res.mat[i][j] %= self.mod
        return res

    def power(self, k):
        tmp = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                tmp.mat[i][j] = self.mat[i][j]
        res = SquareMatrix.id(self.n, self.mod)
        while k:
            if k & 1:
                res = res.multiply(tmp)
            tmp = tmp.multiply(tmp)
            k >>= 1
        return res

    def trace(self):
        res = 0
        for i in range(self.n):
            res += self.mat[i][i]
            res %= self.mod
        return res

    def determinant(self):
        res = 1
        tmp = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                tmp.mat[i][j] = self.mat[i][j]
        for j in range(self.n):
            if tmp.mat[j][j] == 0:
                for i in range(j + 1, self.n):
                    if tmp.mat[i][j] != 0:
                        idx = i
                        break
                else:
                    return 0
                for k in range(self.n):
                    tmp.mat[j][k], tmp.mat[idx][k] = tmp.mat[idx][k], tmp.mat[j][k]
                res *= -1
            inv = SquareMatrix.modinv(tmp.mat[j][j], self.mod)
            for i in range(j + 1, self.n):
                c = -inv * tmp.mat[i][j] % self.mod
                for k in range(self.n):
                    tmp.mat[i][k] += c * tmp.mat[j][k]
                    tmp.mat[i][k] %= self.mod
        for i in range(self.n):
            res *= tmp.mat[i][i]
            res %= self.mod
        return res

    def transpose(self):
        res = SquareMatrix(self.n, self.mod)
        for i in range(self.n):
            for j in range(self.n):
                res.mat[i][j] = self.mat[j][i]
        return res

    def inverse(self): #self.determinant() != 0
        res = SquareMatrix.id(self.n, self.mod)
        tmp = SquareMatrix(self.n, self.mod)
        sgn = 1
        for i in range(self.n):
            for j in range(self.n):
                tmp.mat[i][j] = self.mat[i][j]
        for j in range(self.n):
            if tmp.mat[j][j] == 0:
                for i in range(j + 1, self.n):
                    if tmp.mat[i][j] != 0:
                        idx = i
                        break
                else:
                    return 0
                for k in range(self.n):
                    tmp.mat[j][k], tmp.mat[idx][k] = tmp.mat[idx][k], tmp.mat[j][k]
                    res.mat[j][k], res.mat[idx][k] = res.mat[idx][k], res.mat[j][k]
            inv = SquareMatrix.modinv(tmp.mat[j][j], self.mod)
            for k in range(self.n):
                tmp.mat[j][k] *= inv
                tmp.mat[j][k] %= self.mod
                res.mat[j][k] *= inv
                res.mat[j][k] %= self.mod
            for i in range(self.n):
                c = tmp.mat[i][j]
                for k in range(self.n):
                    if i == j:
                        continue
                    tmp.mat[i][k] -= tmp.mat[j][k] * c
                    tmp.mat[i][k] %= self.mod
                    res.mat[i][k] -= res.mat[j][k] * c
                    res.mat[i][k] %= self.mod
        return res

    def linear_equations(self, vec): #self.determinant != 0
        return self.inverse().operate(vec)

    def print(self):
        print(*self.mat, sep='\n')

MOD = 1000000007

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

M = SquareMatrix(N)
M.set(A)

P = M.power(K)

res = 0

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
MOD = 1_000_000_007
def dot_MOD(x1, x2, MOD):
    """行列の積とＭＯＤ

    ＭＯＤを取りつつ行列の積をもとめる。

    Args:
        x1 (2Dndarry of int): 被積の行列
        x2 (2Dndarry of int): 加積の行列

    Returns:
        ret (2Dndarry of int): 求まった行列

    Raises:
        例外の名前: 例外の説明 (例 : 引数が指定されていない場合に発生 )

    Yields:
        戻り値の型: 戻り値についての説明

    Examples:
        関数の使い方について記載

    Note:
        注意事項などを記載

    """
    ret = np.zeros((x1.shape[1],x2.shape[0]), dtype='int64')
    for i in range(x1.shape[0]):
        for j in range(x2.shape[1]):
            tem = np.mod(x1[i,:] * (x2[:,j][np.newaxis:]), MOD, dtype='int64')
            ret[i][j] = np.mod(tem.sum(), MOD, dtype='int64')
    return ret

def x2_MOD(x, MOD):
    """行列の自冪とＭＯＤ

    ＭＯＤを取りつつ行列の自冪をもとめる。

    Args:
        x1 (2Dndarry of int): 行列

    Returns:
        ret (2Dndarry of int): 求まった行列

    Raises:
        例外の名前: 例外の説明 (例 : 引数が指定されていない場合に発生 )

    Yields:
        戻り値の型: 戻り値についての説明

    Examples:
        関数の使い方について記載

    Note:
        注意事項などを記載

    """
    ret = np.zeros(x.shape, dtype='int64')
    for i in range(x.shape[0]):
        for j in range(x.shape[0]):
            tem = np.mod(x[i,:] * (x[:,j][np.newaxis:]), MOD, dtype='int64')
            ret[i][j] = np.mod(tem.sum(), MOD, dtype='int64')
    return ret

N, K = map(int, input().split())
A = np.array(list(map(int, read().split())), dtype='int64').reshape((N, N))
ans = np.eye(N, dtype='int64')
while K:
    if K&1:
        ans = dot_MOD(ans,A,MOD)
    A = x2_MOD(A, MOD)
    K >>= 1
print(np.mod(ans.sum(), MOD, dtype='int64'))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
MOD = 1_000_000_007

def dot_MOD(x1, x2, MOD):
    """行列の積とＭＯＤ

    ＭＯＤを取りつつ行列の積をもとめる。

    Args:
        x1 (2Dndarry of int): 被積の行列
        x2 (2Dndarry of int): 加積の行列

    Returns:
        ret (2Dndarry of int): 求まった行列

    Raises:
        例外の名前: 例外の説明 (例 : 引数が指定されていない場合に発生 )

    Yields:
        戻り値の型: 戻り値についての説明

    Examples:
        関数の使い方について記載

    Note:
        注意事項などを記載

    """
    if x1.shape[1] != x2.shape[0]:
        return 0
    ret = np.zeros((x1.shape[1],x2.shape[0]), dtype='int64')
    for i in range(x1.shape[0]):
        for j in range(x2.shape[1]):
            tem = np.mod(x1[i,:] * (x2[:,j][np.newaxis:]), MOD, dtype='int64')
            ret[i][j] = np.mod(tem.sum(), MOD, dtype='int64')
    return ret

N, K = map(int, input().split())
A = np.array(list(map(int, read().split())), dtype='int64').reshape((N, N))
ans = np.eye(N, dtype='int64')
while K:
    if K&1:
        ans = dot_MOD(ans,A,MOD)
    A = dot_MOD(A, A, MOD)
    K >>= 1
print(np.mod(ans.sum(), MOD, dtype='int64'))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MOD = 10**9 + 7

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

    maxD = K.bit_length() - 1

    dp = [[[0]*(N) for j in range(N)] for i in range(maxD+1)]
    for v, As in enumerate(Ass):
        nums = [0] * N
        for v2, A in enumerate(As):
            if A == 1:
                nums[v2] += 1
        dp[0][v] = nums
    for d in range(1, maxD+1):
        for v in range(N):
            nums = [0] * N
            for v2, num2 in enumerate(dp[d-1][v]):
                for v3, num3 in enumerate(dp[d-1][v2]):
                    nums[v3] += num2 * num3
                    nums[v3] %= MOD
            dp[d][v] = nums

    anss = [1] * N
    for d in range(maxD+1):
        if K & (1<<d):
            ans2s = [0] * N
            for v in range(N):
                for v2, num in enumerate(dp[d][v]):
                    ans2s[v2] += anss[v] * num
                    ans2s[v2] %= MOD
            anss = ans2s

    print(sum(anss) % MOD)


solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def solve():
    MOD = 10**9 + 7

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

    maxD = K.bit_length() - 1

    dp = [[Counter() for _ in range(N)] for _ in range(maxD+1)]
    for v, As in enumerate(Ass):
        v2s = []
        for v2, A in enumerate(As):
            if A == 1:
                v2s.append(v2)
        dp[0][v] = Counter(v2s)
    for d in range(1, maxD+1):
        for v in range(N):
            for v2, num2 in dp[d-1][v].items():
                for v3, num3 in dp[d-1][v2].items():
                    dp[d][v][v3] += num2 * num3
                    dp[d][v][v3] %= MOD

    anss = [1] * N
    for d in range(maxD+1):
        if K & (1<<d):
            ans2s = [0] * N
            for v in range(N):
                for v2, num in dp[d][v].items():
                    ans2s[v2] += anss[v] * num
                    ans2s[v2] %= MOD
            anss = ans2s

    print(sum(anss) % MOD)


solve()

Submission status: Time Limit Exceeded

Solution code:
def pow(mat, k, mod):
    n = len(mat)
    if k == 0:
        return [[1 if i == j else 0 for i in range(n)] for j in range(n)]
    if k % 2 == 0:
        sqrt_mat = pow(mat, k // 2, mod)
        # calculate 'sqrt_mat * sqrt_mat'
        ret = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                v = 0
                for k in range(n):
                    v += sqrt_mat[i][k] * sqrt_mat[k][j]
                    v %= mod
                ret[i][j] = v
        return ret
    else:
        powmat = pow(mat, k - 1, mod)
        # calculate 'mat * powmat'
        ret = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                v = 0
                for k in range(n):
                    v += mat[i][k] * powmat[k][j]
                    v %= mod
                ret[i][j] = v
        return ret


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    D = pow(A, K, MOD)
    ans = 0
    for i in range(N):
        for j in range(N):
            ans += D[i][j]
            ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from numpy.linalg import matrix_power
from numpy import matrix

class mint:
    def __init__(self, i, mod=10 ** 9 + 7):
        self.mod = mod
        self.i = i % mod
    def __add__(self, other):
        return mint(self.i + other.i)
    def __mul__(self, other):
        return mint(self.i * other.i)
    def __str__(self):
        return str(self.i)

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

print(matrix_power(A, K).sum())

Submission status: Time Limit Exceeded

Solution code:
from numpy.linalg import matrix_power
from numpy import mat

class mint:
    def __init__(self, i, mod=10 ** 9 + 7):
        self.mod = mod
        self.i = i % mod
    def __add__(self, other):
        return mint(self.i + other.i)
    def __mul__(self, other):
        return mint(self.i * other.i)
    def __str__(self):
        return str(self.i)

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

print(matrix_power(A, K).sum())

Submission status: Time Limit Exceeded

Solution code:
from numpy.linalg import matrix_power

mod = 10 ** 9 + 7
class mint:
    def __init__(self, i):
        self.i = i % mod
    def __add__(self, other):
        return mint(self.i + other.i)
    def __mul__(self, other):
        return mint(self.i * other.i)
    def __str__(self):
        return str(self.i)

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

print(matrix_power(A, K).sum())

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint 
from random import randint 


mod=10**9+7
def mutiply_mat(a,b,n):
	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]+=a[i][k]*b[k][j]
				ans[i][j]%=mod
	return ans 

def binary_exp(mat,b,n):
	pass
	# ans=1
	# while b>0:
	# 	if b%2==1:
	# 		ans*=a
	# 	a*=a
	# 	b//=2
	# return ans

def walk(n,k,arr):
	# print(arr)
	ans=[[0]*n for _ in range(n)]
	for i in range(n):
		ans[i][i]=1

	while k>0:
		if k%2==1:
			ans=mutiply_mat(ans,arr,n)
		arr=mutiply_mat(arr,arr,n)
		k//=2

	res=0
	for i in range(n):
		for j in range(n):
			res+=ans[i][j]

	# print (res)
	# pprint(ans)
	return res






n,k=map(int,input().split())
arr=[]
for i in range(n):	
	arr.append(list(map(int,input().split())))
res=walk(n,k,arr)
print(res%(10**9+7))

Submission status: Time Limit Exceeded

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

# nxnの行列積


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


def matrix_exponents(A, t):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        res[i][i] = 1

    while t:
        if t & 1 == 1:
            res = matrix_product(res, A)
        A = matrix_product(A, A)
        t //= 2
    return res


temp = matrix_exponents(AA, kk)


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7

class Matrix(list):

    def mul(self,B,mod = 0):
        C = Matrix([[0] * len(B[0]) for _ in range(len(self))])
        if mod == 0:
            for i in range(len(self)):
                for k in range(len(B)):
                    for j in range(len(B[0])):
                        C[i][j] += self[i][k] * B[k][j]
            
            return C
        else:
            for i in range(len(self)):
                for k in range(len(B)):
                    for j in range(len(B[0])):
                        C[i][j] = (C[i][j] + self[i][k] * B[k][j]) % mod
            
            return C

    
    def pow(self,n,mod = 0):
        if len(self) != len(self[0]):
            raise ValueError('the size of matrix is different')

        if mod == 0:
            B = Matrix([[0] * len(self) for _ in range(len(self))])
            A = self
            for i in range(len(self)):
                B[i][i] = 1
            
            while n > 0:
                if (n&1):
                    B = B.mul(A)
                A = A.mul(A)
                n //= 2
            
            return B

        else:
            B = Matrix([[0] * len(self) for _ in range(len(self))])
            A = self
            for i in range(len(self)):
                B[i][i] = 1
            
            while n > 0:
                if (n&1):
                    B = B.mul(A,mod)
                A = A.mul(A,mod)
                n //= 2
            
            return B

def main():
    N,K = map(int,input().split())
    A = Matrix([list(map(int,input().split())) for _ in range(N)])
    B = A.pow(K,MOD)
    ans = sum(sum(B[i])%MOD for i in range(N))%MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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))

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
mod = 10**9+7

def matrixmul(A, B):
    n = len(A)
    C = []
    for i in range(n):
        c = []
        for j in range(n):
            num = 0
            for k in range(n):
                num = (A[i][k]*B[k][j] + num)%mod
            c.append(num)
        C.append(c)
    return C

now = [[1 if i == j else 0 for i in range(N)] for j in range(N)]        

while K:
    if K&1 == 1:
        now = matrixmul(now, A)
    K //= 2
    A = matrixmul(A, A)

ans = 0
for i in range(N):
    for j in range(N):
        ans = (now[i][j]+ans)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
mod = 10**9+7

def matrixmul(A, B):
    n = len(A)
    C = []
    for i in range(n):
        c = []
        for j in range(n):
            num = 0
            for k in range(n):
                num = (A[i][k]*B[k][j] + num)%mod
            c.append(num)
        C.append(c)
    return C

def matrixpow(A, n):
    if n == 1:
        return A
    if n&1 == 1:
        return matrixmul(matrixpow(A, n-1), A)
    else:
        return matrixmul(matrixpow(A, n//2), matrixpow(A, n//2))
    
An = matrixpow(A, K)
ans = 0
for i in range(N):
    for j in range(N):
        ans = (An[i][j]+ans)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
mod = 10**9+7

def matrixmul(A, B):
    n = len(A)
    C = []
    for i in range(n):
        c = [sum([A[i][k]*B[k][j] for k in range(n)])%mod for j in range(n)]
        C.append(c)
    return C

def matrixpow(A, n):
    if n == 1:
        return A
    if n&1 == 1:
        return matrixmul(matrixpow(A, n-1), A)
    else:
        return matrixmul(matrixpow(A, n//2), matrixpow(A, n//2))
    
An = matrixpow(A, K)
ans = 0
for i in range(N):
    for j in range(N):
        ans = (An[i][j]+ans)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
mod = int(1e+9) + 7
base = [list(map(int, input().split())) for _ in range(N)]
mat = [[0 for _ in range(N)] for __ in range(N)]
for i in range(N):
  mat[i][i] = 1
Mat = [[0 for _ in range(N)] for __ in range(N)]
Base = [[0 for _ in range(N)] for __ in range(N)]
while K != 0:
  for i in range(N):
    for j in range(N):
      Mat[i][j] = mat[i][j]
      Base[i][j] = base[i][j]
  if K % 2 == 1:
    for i in range(N):
      for j in range(N):
        S = 0
        for k in range(N):
          S += Mat[i][k] * Base[k][j]
          S %= mod
        mat[i][j] = S
  for i in range(N):
    for j in range(N):
      S = 0
      for k in range(N):
        S += Base[i][k] * Base[k][j]
        S %= mod
      base[i][j] = S
  K //= 2
X = 0
for i in range(N):
  for j in range(N):
    X += mat[i][j]
    X %= mod
print(X)

Submission status: Time Limit Exceeded

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
n,k=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
dp=[[0]*n for i in range(n)]
mod=10**9+7
for i in range(n):
    for j in range(n):
        dp[i][i]=1
def dot(A,B):
    C=[[0]*n for i 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
while k:
    if k&1:
        dp=dot(dp,a)
    a=dot(a,a)
    k>>=1
ans=0
for i in dp:
    ans+=sum(i)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
(n,k),*a=[list(map(int,t.split()))for t in open(0)]
r=a if k&1else[[i==j for j in range(n)]for i in range(n)]
d=a
for i in range(1,k.bit_length()):
  p=[]
  for y in d:
    q=[0]*n
    for x,s in zip(y,d):
      for j,t in enumerate(s):
        q[j]+=t*x%M
    p+=q,
  d=p
  if 1<<i&k:
    p=[]
    for y in r:
      q=[0]*n
      for x,s in zip(y,d):
        for j,t in enumerate(s):
          q[j]+=t*x%M
      p+=q,
    r=p
print(sum(t for s in r for t in s)%M)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

def power(base, exp, op=lambda x, y: x * y, ie=1):
    res = ie
    while exp:
        if exp & 1:
            res = op(res, base)
        base = op(base, base)
        exp >>= 1
    return res

matrix_id = [[i == j for j in range(N)] for i in range(N)]

def matrix_mul(A, B):
    res = [[0 for j in range(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

P = power(A, K, matrix_mul, matrix_id)

res = 0

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())

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

def mod_pow(matrix, n, mod): #行列累乗を求める
    # print (matrix)
    N = len(matrix[0])
    if n == 0:
        lst = [[1 if i == j else 0 for i in range(N)] for j in range(N)]
        return lst
    lst = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # print (i, j, k)
                lst[i][j] += matrix[i][k] * matrix[k][j]
            lst[i][j] %= mod
    res = mod_pow(lst, n // 2, mod)

    lst = [[0] * N for _ in range(N)]
    if n % 2 == 1:
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    lst[i][j] += res[i][k] * matrix[k][j]
                lst[i][j] %= mod
        return lst
    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: Time Limit Exceeded

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):
            for k in range(K):
                C[i][j] += (A[i][k] * B[k][j]) % MOD
                C[i][j] %= 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)