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
| #include<bits/stdc++.h>
#define mo 1000000007
#define md(a) ((a)%mo)
#define ll long long
#define fsb(a,b,c) for(int a=b;a<=c;a++)
#define fbs(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
struct mt{
ll a[5][5];
}s,c;
ll n;
inline mt times(mt a,mt b){
mt ans;memset(ans.a,0,sizeof(ans.a));
fsb(i,1,2)fsb(j,1,2)fsb(k,1,2)ans.a[i][j]=md(ans.a[i][j]+a.a[i][k]*b.a[k][j]);
return ans;
}
inline mt po(mt a,ll y){
mt ans=a,t=a;y--;
while(y>0){
if(y&1)ans=times(ans,t);
t=times(t,t);
y>>=1;
}
return ans;
}
int main(){
scanf("%lld",&n);
s.a[1][1]=s.a[2][1]=1;
c.a[1][1]=c.a[1][2]=c.a[2][1]=1;
if(n<=2){
puts("1");return 0;
}
printf("%lld\n",times(po(c,n-2),s).a[1][1]);
return 0;
}
|