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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
const int SIZE = 2;
struct Matrix
{
int m[SIZE][SIZE];

void clear()
{
memset(m,0,sizeof m);
}

void init()
{
memset(m,0,sizeof m);
for(int i=0;i<SIZE;++i) m[i][i]=1;
}

void print()
{
for(int i=0;i<SIZE;++i){
for(int j=0;j<SIZE;++j)
printf("%d ",m[i][j]);
puts("");
}
}

Matrix operator+(const Matrix rhs) const
{
Matrix t;
for(int i=0;i<SIZE;++i)
for(int j=0;j<SIZE;++j)
t.m[i][j] = (m[i][j] + rhs.m[i][j]) % mod;
return t;
}

Matrix operator*(const Matrix rhs) const
{
Matrix c;
for(int i=0;i<SIZE;++i)
for(int j=0;j<SIZE;++j)
{
c.m[i][j] = 0;
for(int k=0;k<SIZE;++k)
c.m[i][j] = (c.m[i][j] + m[i][k] * rhs.m[k][j]) % mod;
}
return c;
}

Matrix operator^(int n) const
{
Matrix a,b;
a = *this;
b.init();
while(n)
{
if(n&1) b = b*a;
n>>=1;
a = a*a;
}
return b;
}


} M;

Matrix sum(int n) // a^1 + a^2 + ... + a^n
{
if(n==1) return M;
Matrix temp = sum(n>>1);
if(n&1)
{
Matrix t = M^((n>>1) + 1);
return temp*t + temp + t;
}
else
return temp*(M^(n>>1)) + temp;
}