#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define MAX_N (1<<19)
#define INF 100000000
#define MOD 1000000007
#define RANK 1000000000
#define EPS 1e-10
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> IP;

ll fib(ll x){
    x--;
    ll f1 = 1,f = 1;
    ll r1 = 1,r = 1;
    ll tmp;
    while(x){
        if(x&1){
            tmp = r1;
            r1 = (f1*r1+f*r)%MOD;
            r = (f1*r+f*(tmp-r+5LL*MOD))%MOD;
        }
        tmp = f1;
        f1 = (f1*f1+f*f)%MOD;
        f = f*(2*tmp-f+5LL*MOD)%MOD;
        x >>= 1;
    }
    return r;
}

ll k, sqk;
ll now = 0;
ll sum = 0;

int main(){
    cin >> k;
    if(k == 1){
        cout << 1 << endl;
        return 0;
    }
    if(k == 2){
        cout << 2 << endl;
        return 0;
    }
    sqk = (ll)sqrt(k);
    for(ll i = max(1LL,sqk-10); i < sqk+10; i++){
        if(i*(i+1) < k){
            continue;
        }
        now = i;
        break;
    }
    sum = now*(now-1);
    if(sum+now >= k){
        ll gu = (now*2-2)/4;
        if(sum+gu+1 >= k){
            now *= 2;
            cout << (fib(now-(k-sum-1)*2)*fib(2+(k-sum-1)*2))%MOD << endl;
        } else{
            ll ki = sum+now-k;
            now = now*2+1;
            cout << (fib(now-2*(ki+1))*fib(1+2*(ki+1)))%MOD << endl;
        }
    } else{
        sum += now;
        now *= 2;
        cout << (fib(now+1-(k-sum-1)*2)*fib(2+(k-sum-1)*2))%MOD << endl;
    }
}
### Prompt

Your challenge is to write a Cpp solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define MAX_N (1<<19)
#define INF 100000000
#define MOD 1000000007
#define RANK 1000000000
#define EPS 1e-10
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> IP;

ll fib(ll x){
    x--;
    ll f1 = 1,f = 1;
    ll r1 = 1,r = 1;
    ll tmp;
    while(x){
        if(x&1){
            tmp = r1;
            r1 = (f1*r1+f*r)%MOD;
            r = (f1*r+f*(tmp-r+5LL*MOD))%MOD;
        }
        tmp = f1;
        f1 = (f1*f1+f*f)%MOD;
        f = f*(2*tmp-f+5LL*MOD)%MOD;
        x >>= 1;
    }
    return r;
}

ll k, sqk;
ll now = 0;
ll sum = 0;

int main(){
    cin >> k;
    if(k == 1){
        cout << 1 << endl;
        return 0;
    }
    if(k == 2){
        cout << 2 << endl;
        return 0;
    }
    sqk = (ll)sqrt(k);
    for(ll i = max(1LL,sqk-10); i < sqk+10; i++){
        if(i*(i+1) < k){
            continue;
        }
        now = i;
        break;
    }
    sum = now*(now-1);
    if(sum+now >= k){
        ll gu = (now*2-2)/4;
        if(sum+gu+1 >= k){
            now *= 2;
            cout << (fib(now-(k-sum-1)*2)*fib(2+(k-sum-1)*2))%MOD << endl;
        } else{
            ll ki = sum+now-k;
            now = now*2+1;
            cout << (fib(now-2*(ki+1))*fib(1+2*(ki+1)))%MOD << endl;
        }
    } else{
        sum += now;
        now *= 2;
        cout << (fib(now+1-(k-sum-1)*2)*fib(2+(k-sum-1)*2))%MOD << endl;
    }
}
```