-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path11443.cpp
More file actions
36 lines (32 loc) · 696 Bytes
/
11443.cpp
File metadata and controls
36 lines (32 loc) · 696 Bytes
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
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll mod = 1e9+7;
map<ll, ll> dp;
ll fibo(ll n) {
if (n == 1 || n == 2) return 1;
if (dp.count(n)) return dp[n];
ll result =0;
if (n % 2) {
ll k = (n+1)/2;
ll c = fibo(k);
ll d = fibo(k-1);
result= (c* c + d*d)%mod;
} else {
ll k = n/2;
ll c = fibo(k);
ll d = fibo(k-1);
result= ((2*d + c)*c)%mod;
}
return dp[n]=result;
}
void solve(){
ll a; cin >> a;
cout << (fibo(a+(a%2==0))+mod-1)%mod;
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
solve();
return 0;
}