1 #include <cstdio> 2 #include <cstring> 3 #define LL long long 4  5 LL n; 6 const int p = 1e9 + 7; 7  8 struct Matrix 9 {10     LL a[2][2];11     Matrix()12     {13         memset(a, 0, sizeof(a));14     }15 };16 17 inline Matrix operator * (const Matrix x, const Matrix y)18 {19     Matrix ans;20     int i, j, k;21     for(i = 0; i < 2; i++)22         for(j = 0; j < 2; j++)23             for(k = 0; k < 2; k++)24                 ans.a[i][j] = (ans.a[i][j] + x.a[i][k] * y.a[k][j]) % p;25     return ans;26 }27 28 inline int pow(LL x)29 {30     Matrix ans, trs;31     ans.a[0][0] = ans.a[1][1] = 1;32     trs.a[0][0] = trs.a[1][0] = trs.a[0][1] = 1;33     while(x)34     {35         if(x & 1) ans = ans * trs;36         trs = trs * trs;37         x >>= 1;38     }39     return ans.a[0][0];40 }41 42 int main()43 {44     scanf("%lld", &n);45     printf("%d\n", pow(n - 1));46     return 0;47 }