Language: C++

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include <fstream>
#include <time.h>
#include <iterator>
#include <nmmintrin.h>
#include <intrin.h>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()
using namespace std;
int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 500050;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll add(ll x, ll y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
ll sub(ll x, ll y) {
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
ll mult(ll x, ll y) {
	return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
	if (p == 0) return 1;
	if (p & 1) return mult(x, bin_pow(x, p - 1));
	return bin_pow(mult(x, x), p / 2);
}

int A[55][55];
int N, K;
ll popcnt(ll bit) {
	int cnt = 0;
	REP(i, 60) {
		if (bit&(1LL << i))cnt++;
	}
	return cnt;
}

//aからbまでの長さ2^kの有向パスの数
int dp[55][55][60];
//aからbまでの長さkの有向パスの数
int func(int a,int b, int k) {
	//printf("k=%lld\n", k);
	if (k == 1) {
		int ans;
		if (A[a][b] == 1)ans=1;
		else ans = 0;
		dp[a][b][0] = ans;
		//printf("%lld %lld %lld:%lld\n", a, b, k, ans);
		return ans;
	}
	if (k % 2 == 0) {
		int ans = 0;
		int cnt = popcnt(k);
		//kが2べきのとき
		if (cnt == 1) {
			int x = k;
			int c = 0;
			while (x > 1) {
				x /= 2;
				c++;
			}
			if (dp[a][b][c] != 0) {
				return dp[a][b][c];
			}
			REP(x, N) {
				int res1 = func(a, x, k / 2);
				int res2 = func(x, b, k / 2);
				if (res1 == 0 || res2 == 0) {
					continue;
				}
				ans = add(ans, mult(res1, res2));

			}
			//printf("%lld %lld %lld:%lld\n", a, b, k, ans);
			dp[a][b][c] = ans;
			return ans;
		}
		REP(x, N) {
			int res1 = func(a, x, k / 2);
			int res2 = func(x, b, k / 2);
			if (res1 == 0 || res2 == 0) {
				continue;
			}
			ans = add(ans,mult(res1,res2));

		}
		//printf("%lld %lld %lld:%lld\n", a, b, k, ans);
		return ans;
	}
	else {
		int ans = 0;
		REP(x, N) {
			int res1 = func(a, x, 1);
			int res2 = func(x, b, k - 1);
			if (res1 == 0 || res2 == 0)continue;
			ans = add(ans, mult(res1, res2));
		}
		//printf("%lld %lld %lld:%lld\n", a, b, k, ans);
		return ans;
	}
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> K;
	REP(i, N) {
		REP(j, N) {
			cin >> A[i][j];
		}
	}
	int ans = 0;
	REP(i, N) {
		REP(j, N) {
			ans = add(ans, func(i, j, K));
			//printf("%lld %lld:%lld\n", i, j, func(i, j, K));
		}
	}
	print(ans);
	/*REP(i, N) {
		REP(j, N) {
			pe(A[i][j]);
		}cout << endl;
	}*/
	/*int x; cin >> x;
	print(popcnt(x));*/
	/*while (true) {
		int x, y, k;
		cin >> x >> y >> k;
		if (k == 0)break;
		print(func(x, y, k));
	}*/
}


Compiler output:
a.cc:21:10: fatal error: intrin.h: No such file or directory
   21 | #include <intrin.h>
      |          ^~~~~~~~~~
compilation terminated.