matrix.cpp

template<typename T, size_t n, size_t m>
using matrix = array<array<T, m>, n>;

template<typename T, size_t n >
matrix<T, n, n> get_one_matrix()
{
	matrix<T, n, n> res;
	for (size_t i = 0; i < n; i++)
		for (size_t j = 0; j < n; j++)
			res[i][j] = 0;

	for (size_t i = 0; i < n; i++)	
		res[i][i] = 1;
	return res;
}

template<typename T, size_t n, size_t m, size_t z>
matrix<T, n, z> mult(matrix<T, n, m>& a, matrix<T, m, z>& b)
{
	matrix<T, n, z> res;
	for (size_t i = 0; i < n; i++)
		for (size_t j = 0; j < z; j++)
			res[i][j] = 0;

	for (size_t i = 0; i < n; i++)
		for (size_t j = 0; j < m; j++)
			for(size_t c = 0; c < z; c++)	
				res[i][c] += a[i][j] * 1ll * b[j][c];

	return res;
}

template<typename T, size_t n>
matrix<T, n, n> binpow(matrix<T, n, n>& t, ll p)
{
	matrix<T, n, n> res = get_one_matrix<T, n>();

	while (p)
	{
		if (p & 1) res = mult(res, t);

		t = mult(t, t);
		p >>= 1;
	}

	return res;	
}