12345678910111213141516171819202122232425262728293031323334 |
- #include <bits/stdc++.h>
-
- using namespace std;
- typedef unsigned long long LL;
- const int MAXN = 1000000 + 10;
- const LL MOD = 1000000007;
- LL f[MAXN][2][2] = {0};
-
- inline LL mpower(LL a, int x) {
- a %= MOD;
- if (x == 1 || a == 0)return a;
- if (x == 0)return 1;
- if (x & 1) return (a * mpower(a * a % MOD, x >> 1)) % MOD;
- return mpower(a * a % MOD, x >> 1);
- }
-
- int main() {
- int n;
- cin >> n;
- if (n < 3) {
- cout << 0 << endl;
- return 0;
- }
-
- f[3][0][0] = f[3][0][1] = f[3][1][0] = 2, f[3][1][1] = 1;
- for (int i = 4; i <= n; i++) {
- f[i][0][0] = (f[i - 1][0][0] + f[i - 1][0][1]) % MOD;
- f[i][0][1] = (f[i - 1][1][1] + f[i - 1][1][0]) % MOD;
- f[i][1][0] = (f[i - 1][0][0] + f[i - 1][0][1]) % MOD;
- f[i][1][1] = f[i - 1][1][0];
- }
- cout << ((mpower(2, n) - (f[n][0][0] + f[n][0][1] + f[n][1][0] + f[n][1][1])) % MOD + MOD) % MOD << endl;
- return 0;
- }
|