public class Matrix {
static int N; // size of the matrix
/**
* compute pow(base, pow)
* O(N^3) * logN
**/
static long[][] matrixPower(long [][] base, long pow) {
long [][] ans = new long [N][N];
// generate identity matrix
for (int i = 0; i < N; i++) ans[i][i] = 1;
// binary exponentiation
while ( pow != 0 ) {
if ( (pow&1) != 0 ) ans = multiplyMatrix(ans, base);
base = multiplyMatrix(base, base);
pow >>= 1;
}
return ans;
}
/**
* compute m * m2
* O(N^3)
**/
static long [][] multiplyMatrix(long [][] m, long [][] m2) {
long [][] ans = new long [N][N];
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
ans[i][j] = 0;
for (int k = 0; k < N; k++) {
ans[i][j] += m[i][k] * m2[k][j];
}
}
return ans;
}
}
cHVibGljIGNsYXNzIE1hdHJpeCB7CgoKCXN0YXRpYyBpbnQgTjsJLy8gc2l6ZSBvZiB0aGUgbWF0cml4CgoJLyoqCgkgKiBjb21wdXRlIHBvdyhiYXNlLCBwb3cpCgkgKiBPKE5eMykgKiBsb2dOCgkqKi8KCXN0YXRpYyBsb25nW11bXSBtYXRyaXhQb3dlcihsb25nIFtdW10gYmFzZSwgbG9uZyBwb3cpCXsKCQlsb25nIFtdW10gYW5zID0gbmV3IGxvbmcgW05dW05dOwoJCS8vIGdlbmVyYXRlIGlkZW50aXR5IG1hdHJpeAoJCWZvciAoaW50IGkgPSAwOyBpIDwgTjsgaSsrKQlhbnNbaV1baV0gPSAxOwoJCQoJCS8vIGJpbmFyeSBleHBvbmVudGlhdGlvbgoJCXdoaWxlICggcG93ICE9IDAgKQl7CgkJCWlmCSggKHBvdyYxKSAhPSAwICkJYW5zID0gbXVsdGlwbHlNYXRyaXgoYW5zLCBiYXNlKTsKCQkJCgkJCWJhc2UgPSBtdWx0aXBseU1hdHJpeChiYXNlLCBiYXNlKTsKCQkJCgkJCXBvdyA+Pj0gMTsKCQl9CgkJCgkJcmV0dXJuCWFuczsKCX0KCgkvKioKCSAqIGNvbXB1dGUgbSAqIG0yCgkgKiBPKE5eMykKCSoqLwoJc3RhdGljIGxvbmcgW11bXSBtdWx0aXBseU1hdHJpeChsb25nIFtdW10gbSwgbG9uZyBbXVtdIG0yKQl7CgkJbG9uZyBbXVtdIGFucyA9IG5ldyBsb25nIFtOXVtOXTsKCQkKCQlmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykJZm9yIChpbnQgaiA9IDA7IGogPCBOOyBqKyspCXsKCQkJYW5zW2ldW2pdID0gMDsKCQkJZm9yIChpbnQgayA9IDA7IGsgPCBOOyBrKyspCXsKCQkJCWFuc1tpXVtqXSArPSBtW2ldW2tdICogbTJba11bal07CgkJCX0KCQl9CgoJCXJldHVybglhbnM7Cgl9CgkKfQ==