矩阵快速幂模板

class matrix{
public:
	ll a[105][105];
	int n, m;
	matrix(int n, int m) {
		this->n = n;
		this->m = m;
		memset(a, 0, sizeof(a));
	}
	matrix operator *(matrix &b) {
		matrix c(n, b.m);
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= b.m; j++) {
				for(int k = 1; k <= m; k++) {
					c.a[i][j] += a[i][k] * b.a[k][j];
                	if (c.a[i][j] > mod) {
                 	   c.a[i][j] %= mod;
                	}
				}
			}
		}
		return c;
	}
	matrix pow(int x) {
		matrix res(n, n), A(n, n);
		for(int i = 1; i <= n; i++) res.a[i][i] = 1;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				A.a[i][j] = a[i][j];
			}
		}
		while(x) {
			if(x&1) res = res*A;
			A = A*A;
			x >>= 1;
		}
		return res;
	}
};