CodeEff/ECCO huggingface dataset:
# Original solution
import sys
from bisect import bisect_left, bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *ABC = list(map(int, read().split()))
    A = sorted(ABC[:N])
    B = ABC[N : 2 * N]
    C = sorted(ABC[2 * N : 3 * N])

    ans = sum(bisect_left(A, b) * (N - bisect_right(C, b)) for b in B)

    print(ans)
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys
from bisect import bisect_left, bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    A.sort()
    C.sort()

    ans = sum(bisect_left(A, b) * (N - bisect_right(C, b)) for b in B)

    print(ans)
    return


if __name__ == '__main__':
    main()
# Original solution
from sys import stdin
from bisect import bisect_right, bisect_left


def input():
    return stdin.readline().strip()


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    A.sort()
    B.sort()
    C.sort()

    ans = sum(bisect_left(A, b) * (N - bisect_right(C, b)) for b in B)
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys
from bisect import bisect_left, bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    A.sort()
    B.sort()
    C.sort()

    ans = sum(bisect_left(A, b) * (N - bisect_right(C, b)) for b in B)

    print(ans)
    return


if __name__ == '__main__':
    main()
# Original solution
#ABC077 C - Snuke Festival
from bisect import bisect_left, bisect_right
si = lambda: eval(input())
ni = lambda: int(eval(input()))
nm = lambda: list(map(int, input().split()))
nl = lambda: list(map(int, input().split()))

N = ni()
A = nl()
B = nl()
C = nl()

A.sort()
B.sort()
C.sort()
ans = 0

for i in range(N):
    t = 0
    tt = 0
    t = bisect_left(B,C[i])
    for j in range(t,0,-1):
        tt = bisect_left(A,B[j-1])
        ans += tt

print(ans)

# Optimized solution
#ABC077 C - Snuke Festival
from bisect import bisect_left, bisect_right
si = lambda: eval(input())
ni = lambda: int(eval(input()))
nm = lambda: list(map(int, input().split()))
nl = lambda: list(map(int, input().split()))

N = ni()
A = nl()
B = nl()
C = nl()

A.sort()
C.sort()

ans = 0

for i in range(N):
    t = 0
    tt = 0
    t = bisect_left(A,B[i])
    tt = N-bisect_right(C,B[i])
    ans += t*tt

print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()

ans = 0
dict_a = dict()
dict_b = dict()
for i in range(n):
    if a[i] in list(dict_a.keys()):
        b_mid = dict_a[a[i]]
    else:
        left = n - 1
        right = 0
        b_mid = n // 2
        while left >= right:
            if b[b_mid] > a[i]:
                left = b_mid - 1
            else:
                right = b_mid + 1
            b_mid = (left + right) // 2
        b_mid += 1
        dict_a[a[i]] = b_mid

    for j in range(b_mid, n):
        if b[j] in list(dict_b.keys()):
            c_mid = dict_b[b[j]]
        else:
            left = n - 1
            right = 0
            c_mid = n // 2
            while left >= right:
                if c[c_mid] > b[j]:
                    left = c_mid - 1
                else:
                    right = c_mid + 1
                c_mid = (left + right) // 2
            dict_b[b[j]] = c_mid
        ans += n - c_mid - 1
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()

ans = 0
i = []
k = []
for j in range(n):
    left = n - 1
    right = 0
    a_mid = n // 2
    while left >= right:
        if a[a_mid] >= b[j]:
            left = a_mid - 1
        else:
            right = a_mid + 1
        a_mid = (left + right) // 2
    i.append(a_mid + 1)
    
for j in range(n):
    left = n - 1
    right = 0
    c_mid = n // 2
    while left >= right:
        if c[c_mid] > b[j]:
            left = c_mid - 1
        else:
            right = c_mid + 1
        c_mid = (left + right) // 2
    k.append(n - c_mid - 1)

ans = sum(x * y for x, y in zip(i, k))
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()

ans = 0
i = []
k = []
for j in range(n):
    left = n - 1
    right = 0
    a_mid = n // 2
    while left >= right:
        if a[a_mid] >= b[j]:
            left = a_mid - 1
        else:
            right = a_mid + 1
        a_mid = (left + right) // 2
    i.append(a_mid + 1)
    
for j in range(n):
    left = n - 1
    right = 0
    c_mid = n // 2
    while left >= right:
        if c[c_mid] > b[j]:
            left = c_mid - 1
        else:
            right = c_mid + 1
        c_mid = (left + right) // 2
    k.append(n - c_mid - 1)

ans = sum(x * y for x, y in zip(i, k))
print(ans)

# Optimized solution
import bisect

n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()

ans = 0
for j in range(n):
    i = bisect.bisect_left(a, b[j])
    k = n - bisect.bisect_right(c, b[j])
    ans += i * k
print(ans)
# Original solution
def is_ok_under(array, mid, target):
    return array[mid] < target


def is_ok_over(array, mid, target):
    return array[mid] > target


# ok is -1. ng is len(array)
def bSearchUnder(array, ok, ng, target):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok_under(array, mid, target):
            ok = mid
        else:
            ng = mid
    return ok


# ng is -1. ok is len(array)
def bSearchOver(array, ok, ng, target):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok_over(array, mid, target):
            ok = mid
        else:
            ng = mid
    return ok


n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()

ans = 0

for i in range(len(b)):
    add = 1
    add *= bSearchUnder(a, -1, len(a), b[i]) + 1
    add *= len(c) - bSearchOver(c, len(c), -1, b[i])
    ans += add

print(ans)


# Optimized solution
def binSearch(array, num):
    n = len(array)
    l = -1
    r = n

    while l + 1 < r:
        m = (l + r) // 2
        if num <= array[m]:
            r = m
        else:
            l = m

    return r


n = int(eval(input()))

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
c.sort()

ans = 0
for i in range(len(b)):
    a_idx = binSearch(a, b[i])
    c_idx = binSearch(c, b[i] + 1)
    ans += a_idx * (n - c_idx)
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort()
B.sort()
C.sort()
ans = 0
for i in A:
    for j in B:
        for k in C:
            if (i<j)&(j<k):
                ans += 1
print(ans)

# Optimized solution
import bisect
n= int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for i in range(n):
    x = bisect.bisect_left(a,b[i])
    y = bisect.bisect_right(c,b[i])
    ans += x*(n-y)
print(ans)
# Original solution
import bisect

N = int(eval(input()))
A = sorted([int(i) for i in input().split()])
B = sorted([int(i) for i in input().split()])
C = sorted([int(i) for i in input().split()])

cnt = 0
for i in range(N):
    x = bisect.bisect_right(B, A[i])
    for j in B[x:]:
        y = bisect.bisect_right(C, j)
        cnt += N - y
        
print(cnt)

# Optimized solution
import bisect

N = int(eval(input()))
A = sorted([int(i) for i in input().split()])
B = sorted([int(i) for i in input().split()])
C = sorted([int(i) for i in input().split()])

cnt = 0
for b in B:
    cnt += bisect.bisect_left(A, b) * (N - bisect.bisect_right(C, b))
    
print(cnt)
# Original solution
import bisect

n = int(eval(input()))
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
bnum = [n - bisect.bisect_right(c, b[i]) for i in range(n)]
ans = 0
for i in range(n):
  ai = a[i]
  ans += sum(bnum[bisect.bisect_right(b, ai):n])
print(ans)

# Optimized solution
import bisect

n = int(eval(input()))
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
ans = 0
for i in b:
  ai = bisect.bisect_left(a, i)
  ci = n - bisect.bisect_right(c, i)
  ans += ai*ci
print(ans)
# Original solution
def biserch(l,key,flag=True):
    if flag is True:
        func = judge_1
    else:
        func = judge_2
    left = -1; right = len(l)
    while right - left > 1:
        middle = (left+right) // 2
        if func(l,key,middle) is True:
            right = middle
        else:
            left = middle
    return right

def judge_1(l,key,middle):
    if key <= l[middle]:
        return True
    else:
        return False

def judge_2(l,key,middle):
    if key < l[middle]:
        return True
    else:
        return False

N = int(eval(input()))
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))

ans = 0
for b in B:
    top = biserch(A,b)
    bottom = N - biserch(C,b,flag=False)
    ans += top*bottom
print(ans)

# Optimized solution
def biserch_min(l,key):
    left = 0; right = len(l)
    while left < right:
        mid = (left+right)//2
        if l[mid] < key:
            left = mid+1
        else:
            right = mid
    return left

def biserch_max(l,key):
    left = 0; right = len(l)
    while left < right:
        mid = (left+right)//2
        if key < l[mid]:
            right = mid
        else:
            left = mid+1
    return right


N = int(eval(input()))
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))

ans = 0
for b in B:
    top = biserch_min(A,b)
    bottom = N - biserch_max(C,b)
    ans += top*bottom
print(ans)
# Original solution
import bisect

N = int(eval(input()))
lst_a = sorted([int(x) for x in input().split()])
lst_b = sorted([int(x) for x in input().split()])
lst_c = sorted([int(x) for x in input().split()])
ans = 0
for b in lst_b:
    i = bisect.bisect_left(lst_a, b)
    j = bisect.bisect_right(lst_c, b)
    if i > 0 and j != len(lst_c):
        ans += i * (N - j)

print(ans)


# Optimized solution
import bisect

N = int(eval(input()))
lst_a = sorted([int(x) for x in input().split()])
lst_b = sorted([int(x) for x in input().split()])
lst_c = sorted([int(x) for x in input().split()])
ans = 0
for b in lst_b:
    i = bisect.bisect_left(lst_a, b)
    j = bisect.bisect_right(lst_c, b)
    ans += i * (N - j)

print(ans)
# Original solution
import sys
sys.setrecursionlimit(4100000)
input=sys.stdin.readline
# coding: utf-8
# Your code here!

n=int(eval(input()))
a = [list(map(int, input().split())) for _ in range(3)]
a[0].sort()
a[2].sort()
"""
print(a[0])
print(a[1])
print(a[2])
"""
def bin_lower(b):
    if a[0][0]>=b:
        return 0
    pl=0
    pr=n-1
    
    while True:
        pc=(pl+pr)//2
        if a[0][pc]>=b and a[0][pc-1]<b:
            return pc
        elif a[0][pc]<b:
            pl=pc+1
            if pl>n-1:
                return n
        """
        else:
            pr=pc-1
            if pr<0:
                return 0
        """
                
def bin_upper(b):    
    if a[2][n-1]<=b:
        return 0
    pl=0
    pr=n-1
    
    while True:
        pc=(pl+pr)//2
        if a[2][pc]<=b and a[2][pc+1]>b:
            return n-1-pc
        elif a[2][pc]>b:
            pr=pc-1
            if pr<0:
                return n
        """
        else:
            pl=pc+1
            if pl>n-1:
                return 0
        """
"""
print(bin_upper(a[1][0]))
print(bin_lower(a[1][0]))
print(bin_upper(a[1][1]))
print(bin_lower(a[1][1]))
print(bin_upper(a[1][2]))
print(bin_lower(a[1][2]))
"""

cnt=0
for i in range(n):
    cnt+=bin_lower(a[1][i])*bin_upper(a[1][i])
print(cnt)


# Optimized solution

import sys

input = sys.stdin.readline
# coding: utf-8
# Your code here!
n = int(eval(input()))
a = [list(map(int, input().split())) for _ in range(3)]
a[0].sort()
a[2].sort()

def bin_chisaimono(b):
    if a[0][0] >= b:
        return 0
    pl = 0
    pr = n - 1

    while True:
        pc = (pl + pr) // 2
        if pc == n - 1 and a[0][pc] < b:
            return n
        elif a[0][pc] < b <= a[0][pc + 1]:
            return pc + 1
        elif a[0][pc] >= b:
            pr = pc -1
        else:
            pl = pc + 1


def bin_okimono(b):
    if a[2][n - 1] <= b:
        return 0
    pl = 0
    pr = n - 1

    while True:
        pc = (pl + pr) // 2
        if pc == 0 and a[2][pc] > b:
            return n
        elif a[2][pc - 1] <= b < a[2][pc]:
            return n - pc
        elif a[2][pc] <= b:
            pl = pc + 1
        else:
            pr = pc - 1


cnt = 0
for i in range(n):
    cnt += bin_chisaimono(a[1][i]) * bin_okimono(a[1][i])
print(cnt)
# Original solution
import bisect
n=int(eval(input()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()

ab=[]
bc=[]
for i in range(n):
    ab.append(bisect.bisect_left(a, b[i]))
    bc.append(bisect.bisect_left(b, c[i]))

ans=0
for i in bc:
    ans+=sum(ab[:i])

print(ans)

# Optimized solution
import bisect
n=int(eval(input()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
c.sort()

ans=0
for i in b:
    up=bisect.bisect_left(a, i)
    dn=n-bisect.bisect_right(c, i)
    ans+=up*dn

print(ans)
# Original solution
t = eval(input())
lst = list(map(int, input().split()))
a = max(lst)
b = min(lst)
c = sum(lst)
print((str(b) + " " + str(a) + " " + str(c)))

# Optimized solution
t = int(eval(input()))
lst = list(map(int, input().split()))
a = min(lst)
b = max(lst)
c = sum(lst)
print((str(a) + " " + str(b) + " " + str(c)))
# Original solution
n = eval(input())
a = list(map(int,input().split()))
a.sort()
print(a[0],a[n-1],sum(a))

# Optimized solution
n = eval(input())
a = list(map(int,input().split()))
print(min(a),max(a),sum(a))
# Original solution
eval(input())
nums = [int(x) for x in input().split(" ")]
print(("{0} {1} {2}".format(min(nums), max(nums), sum(nums))))

# Optimized solution
line = eval(input())
nums = list(map(int, input().split()))

print(f"{min(nums)} {max(nums)} {sum(nums)}")
# Original solution
from functools import reduce
n = eval(input())
l = sorted(map(int,input().split()))
print(l[0], l[n-1], reduce(lambda x,y: x+y, l))

# Optimized solution
n = eval(input())
l = list(map(int,input().split()))
print(min(l), max(l), sum(l))
# Original solution
# 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=list(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))


# Optimized solution
# 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 = list(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()
# Original solution
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 = list(map(int,input().split()))
mod = 10**9+7

a = [list(map(int,input().split())) for i in range(n)]
a = list(map(list, 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)

# Optimized solution
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 = list(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)
# Original solution
def solve():
    MOD = 10**9 + 7

    N, K = list(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()


# Optimized solution
from operator import mul

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

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

    def getMatrixProduct(Ass, Bss, MOD):
        BssTr = list(map(list, list(zip(*Bss))))
        Ax = len(Ass)
        By = len(Bss[0])
        ansss = [[0]*(By) for _ in range(Ax)]
        for y, Bs in enumerate(BssTr):
            for x, As in enumerate(Ass):
                ansss[x][y] = sum(map(mul, As, Bs)) % MOD
        return ansss
    def getMatrixPower(Ass, n, MOD):
        sizeA = len(Ass)
        ansss = [[0]*(sizeA) for _ in range(sizeA)]
        for i in range(sizeA):
            ansss[i][i] = 1
        while n:
            if n & 1:
                ansss = getMatrixProduct(ansss, Ass, MOD)
            Ass = getMatrixProduct(Ass, Ass, MOD)
            n //= 2
        return ansss

    Pss = getMatrixPower(Ass, K, MOD)

    ans = 0
    for Ps in Pss:
        for P in Ps:
            ans += P
            ans %= MOD

    print(ans)


solve()
# Original solution
N, K = list(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]
            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)


# Optimized solution
N, K = list(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)
# Original solution
N, K = list(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)


# Optimized solution
N, K = list(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)