非常巧妙的一道题，不过也有点套路。

看到 $n$ 很小 $K$ 很大，直接想到矩阵快速幂。
然后不会做了。
嗯？这不是图论吗，怎么在 DP 题单里？
然后想起来 Floyd 本质上是 DP。

所以采用类似于 Floyd 的做法，设 $f_{u,v,k}$ 表示 $u \rightarrow v$ 用 $k$ 步的方案数。
则 $f_{u,v,k} = f_{u,z,k-1} \times f_{z,v,1}$。
其中前者可以递推得到，后者就是 $a$ 数组，时间复杂度 $O(k n^3)$。

其实这个式子和矩阵乘法非常像了，可以直接拿来优化，这就是矩阵快速幂优化 Floyd。
所以最后就是求 $a^k$。

#include <bits/stdc++.h>
using namespace std;
const int N = 55, mod = 1e9 + 7;
int n;
long long k;
struct Matrix {
    int a[N][N];
    void init() {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) a[i][j] = 0;
    }
} a;
Matrix mul(Matrix a, Matrix b) {
    Matrix res; res.init();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                (res.a[i][j] += (a.a[i][k] * 1ll * b.a[k][j]) % mod) %= mod;
    return res;
}
Matrix qmi(Matrix a, long long k) {
    Matrix res; res.init();
    for (int i = 1; i <= n; i++) res.a[i][i] = 1;
    while (k) {
        if (k & 1) res = mul(res, a);
        a = mul(a, a);
        k >>= 1;
    }
    return res;
}
int main() {
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) scanf("%d", &a.a[i][j]);
    a = qmi(a, k);
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) (ans += a.a[i][j]) %= mod;
    printf("%lld\n", ans);
    return 0;
}