Submission #71055352

---

Source Code Expand

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

#define MOD_BY 1000000007

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int mul(int a, int b) {
	return (int)((long long)a * b % MOD_BY);
}

int N;
uint64_t K;
int a[64][64];

void matmul(int x[64][64], int y[64][64], int out[64][64]) {
	int i, j, k;
	int ans[64][64];
	memset(ans, 0, sizeof(ans));
	for (k = 0; k < N; k++) {
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				ans[i][j] = add(ans[i][j], mul(x[i][k], y[k][j]));
			}
		}
	}
	memcpy(out, ans, sizeof(ans));
}

int cur[64][64];

int main(void) {
	int i, j;
	int ans = 0;
	if (scanf("%d%" SCNu64, &N, &K) != 2) return 1;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (scanf("%d", &a[i][j]) != 1) return 1;
		}
		cur[i][i] = 1;
	}
	while (K > 0) {
		if (K & 1) matmul(cur, a, cur);
		matmul(a, a, a);
		K >>= 1;
	}
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			ans = add(ans, cur[i][j]);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result