1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1000000007LL;
const int maxn = 10;
LL n;
LL ret;
typedef struct Matrix {
    LL m[maxn][maxn];
    int r;
    int c;
    Matrix() {
        r = c = 0;
        memset(m, 0, sizeof(m));
    } 
} Matrix;
Matrix mul(Matrix m1, Matrix m2, LL mod) {
    Matrix ans = Matrix();
    ans.r = m1.r;
    ans.c = m2.c;
    for(int i = 1; i <= m1.r; i++) {
        for(int j = 1; j <= m2.r; j++) {
               for(int k = 1; k <= m2.c; k++) {
                if(m2.m[j][k] == 0) continue;
                ans.m[i][k] = ((ans.m[i][k] + m1.m[i][j] * m2.m[j][k] % mod) % mod) % mod;
            }
        }
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX