Buggy python submission (verdict: Runtime Error):
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.ndarray(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()


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys

input = sys.stdin.readline

md = 10 ** 9 + 7
n, k = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(n)], dtype="O")
c = np.eye(n, dtype="O")

while k:
    if k & 1:
        c = np.dot(a, c) % md
    a = np.dot(a, a) % md
    k >>= 1
print(np.sum(c) % md)


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            ck = 0
            for ak, bk in zip(ai, bj):
                ck += ak * bk
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i in range(n):
        ai = a[i]
        for j in range(n):
            ck = 0
            for ak, bk in zip(ai, [bi[j] for bi in b]):
                ck += ak * bk
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def dot(a, b):
    an = len(a)
    bn = len(b[0])
    c = [[0] * bn for _ in range(an)]
    for i in range(an):
        ai = a[i]
        for j in range(bn):
            ck = 0
            for ak, bk in zip(ai, [bi[j] for bi in b]):
                ck += ak * bk
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
e = [[1] * n]
print(sum(dot(e, pwr(a, k))[0]) % md)


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def dot(a, b):
    an = len(a)
    bn = len(b[0])
    c = [[0] * bn for _ in range(an)]
    for i in range(an):
        ai = a[i]
        for j in range(bn):
            ck = 0
            for ak, bk in zip(ai, [bi[j] for bi in b]):
                ck += (ak * bk)
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while k > 0:
        if k & 1:
            if c:
                c = dot(a, c)
            else:
                c = a
        a = dot(a, a)
        k >>= 1
    return c


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


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def dot(a, b):
    an = len(a)
    bn = len(b[0])
    c = [[0] * bn for _ in range(an)]
    for i in range(an):
        ai = a[i]
        for j in range(bn):
            ck = 0
            for ak, bk in zip(ai, [bi[j] for bi in b]):
                ck += (ak * bk) % md
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while k > 0:
        if k & 1:
            if c:
                c = dot(a, c)
            else:
                c = a
        a = dot(a, a)
        k >>= 1
    return c


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


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Time Limit Exceeded):
def dot(a, b):
    an = len(a)
    bn = len(b[0])
    c = [[0] * bn for _ in range(an)]
    for i in range(an):
        ai = a[i]
        for j in range(bn):
            ck = 0
            for ak, bk in zip(ai, [bi[j] for bi in b]):
                ck += ak * bk
                c[i][j] = ck % md
    return c


def pwr(a, k):
    c = None
    while k > 0:
        if k & 1:
            if c:
                c = dot(a, c)
            else:
                c = a
        a = dot(a, a)
        k >>= 1
    return c


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


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

md = 10 ** 9 + 7
n, k = map(int, input().split())
n1 = n + 1
dp = [0]
ko = [[]]
for _ in range(n):
    s = input()
    st = 0
    kk = []
    while 1:
        i = s.find("1", st)
        if i == -1: break
        kk += [i // 2 + 1]
        st = i + 1
    ko += [kk]
    dp += [len(kk)]

for _ in range(k - 1):
    ndp = [0] * n1
    for i in range(1, n1):
        for ki in ko[i]:
            ndp[i] += dp[ki]
            ndp[i] %= md
    dp = ndp

print(sum(dp) % md)


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline

md = 10 ** 9 + 7
n, k = map(int, input().split())
n1 = n + 1
dp = [0]
ko = [[]]
for _ in range(n):
    s = input()
    st = 0
    kk = []
    while 1:
        i = s.find("1", st)
        if i == -1: break
        kk += [i // 2 + 1]
        st = i + 1
    ko += [kk]
    dp += [len(kk)]

for _ in range(k - 1):
    ndp = [0] * n1
    for i in range(1, n1):
        for ki in ko[i]:
            ndp[i] += dp[ki]
            ndp[i] %= md
    dp = ndp

print(sum(dp) % md)


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def ps(i, k):
    if k == 1:
        return len(ko[i])
    t = (i, k)
    if t in memo:
        return memo[t]
    re = 0
    for ki in ko[i]:
        re += ps(ki, k - 1)
        re %= md
        memo[t] = re
    return re


md = 10 ** 9 + 7
n, k = map(int, input().split())
ko = [[]]
memo = {}
for _ in range(n):
    s = input()
    st = 0
    kk = []
    while 1:
        i = s.find("1", st)
        if i == -1: break
        kk += [i // 2 + 1]
        st = i + 1
    ko += [kk]

ans = 0
for i in range(1, n + 1):
    ans += ps(i, k)

print(ans)


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def ps(i, k):
    if k == 1:
        return len(ko[i])
    t = (i, k)
    if t in memo:
        return memo[t]
    re = 0
    for ki in ko[i]:
        re += ps(ki, k - 1)
        re %= md
        memo[t] = re
    return re


md = 10 ** 9 + 7
n, k = map(int, input().split())
ko = [[]]
memo = {}
for _ in range(n):
    s = input()
    st = 0
    kk = []
    while 1:
        i = s.find("1", st)
        if i == -1: break
        kk += [i // 2 + 1]
        st = i + 1
    ko += [kk]

ans = 0
for i in range(1, n + 1):
    ans += ps(i, k)

print(ans)


Fixed submission:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


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