#include<bits/stdc++.h>
using namespace std;

using Int = __int128_t;
Int abs128(Int val){return val<0?-val:val;}

ostream &operator<<(ostream &os,Int val){
  if(ostream::sentry(os)){
    __uint128_t tmp=abs128(val);
    char buf[64];
    char *d=end(buf);
    do{
      --d;
      *d=char(tmp%10+'0');
      tmp/=10;
    }while(tmp);
    if(val<0) *--d='-';
    Int len=end(buf)-d;
    if(os.rdbuf()->sputn(d,len)!=len){
      os.setstate(ios_base::badbit);
    }
  }
  return os;
}

istream &operator>>(istream &is,Int &val){
  string s;
  is>>s;
  val=0;
  for(Int i=0;i<(Int)s.size();i++)
    if(isdigit(s[i])) val=val*10+s[i]-'0';
  if(s[0]=='-') val*=-1;
  return is;
}

Int fib(Int k,const Int mod){
  using arr=vector<Int>;
  using mat=vector<arr>;

  auto mul=[&](const mat &A,const mat &B)->mat{
    mat C(2,arr(2,0));
    for(Int i=0;i<2;i++){
      for(Int j=0;j<2;j++){
	for(Int k=0;k<2;k++)
	  C[i][j]+=A[i][k]*B[k][j];
	C[i][j]%=mod;
      }
    }
    return C;
  };
  
  mat A(2,arr(2,0));
  A[0][0]=A[0][1]=A[1][0]=1;

  mat res(2,arr(2,0));
  res[0][0]=res[1][1]=1;
  
  while(k){
    if(k&1) res=mul(res,A);
    A=mul(A,A);
    k>>=1;
  }
  
  return (res[0][0]+res[0][1])%mod;
};

//INSERT ABOVE HERE
signed main(){
  Int k;
  cin>>k;
  k--;
  
  auto calc=[&](Int x)->Int{
    Int y=(x/2);
    Int res=y*(y+1);
    if(x>y*2) res+=x/2+1;
    return res;
  };
  
  Int l=0,r=1e12;
  while(l+1<r){
    Int m=(l+r)>>1;
    if(calc(m)<=k) l=m;
    else r=m;
  }

  assert(calc(l)<=k);
  assert(calc(r)>k);

  Int a=l/2+1;
  k-=calc(l);
  //cout<<l<<" "<<calc(l)<<":"<<k<<" "<<a<<endl;
  
  const Int MOD = 1e9+7;
  if(k<(a+1)/2){
    cout<<fib(k*2,MOD)*fib(l-k*2,MOD)%MOD<<endl;
    return 0;
  }
  Int b=(a-k)*2-1;
  //cout<<b<<":"<<fib(b,MOD)<<endl;
  //cout<<l-b<<":"<<fib(l-b,MOD)<<endl;
  cout<<fib(b,MOD)*fib(l-b,MOD)%MOD<<endl;
  return 0;
}


### Prompt

Your task is to create a cpp solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

using Int = __int128_t;
Int abs128(Int val){return val<0?-val:val;}

ostream &operator<<(ostream &os,Int val){
  if(ostream::sentry(os)){
    __uint128_t tmp=abs128(val);
    char buf[64];
    char *d=end(buf);
    do{
      --d;
      *d=char(tmp%10+'0');
      tmp/=10;
    }while(tmp);
    if(val<0) *--d='-';
    Int len=end(buf)-d;
    if(os.rdbuf()->sputn(d,len)!=len){
      os.setstate(ios_base::badbit);
    }
  }
  return os;
}

istream &operator>>(istream &is,Int &val){
  string s;
  is>>s;
  val=0;
  for(Int i=0;i<(Int)s.size();i++)
    if(isdigit(s[i])) val=val*10+s[i]-'0';
  if(s[0]=='-') val*=-1;
  return is;
}

Int fib(Int k,const Int mod){
  using arr=vector<Int>;
  using mat=vector<arr>;

  auto mul=[&](const mat &A,const mat &B)->mat{
    mat C(2,arr(2,0));
    for(Int i=0;i<2;i++){
      for(Int j=0;j<2;j++){
	for(Int k=0;k<2;k++)
	  C[i][j]+=A[i][k]*B[k][j];
	C[i][j]%=mod;
      }
    }
    return C;
  };
  
  mat A(2,arr(2,0));
  A[0][0]=A[0][1]=A[1][0]=1;

  mat res(2,arr(2,0));
  res[0][0]=res[1][1]=1;
  
  while(k){
    if(k&1) res=mul(res,A);
    A=mul(A,A);
    k>>=1;
  }
  
  return (res[0][0]+res[0][1])%mod;
};

//INSERT ABOVE HERE
signed main(){
  Int k;
  cin>>k;
  k--;
  
  auto calc=[&](Int x)->Int{
    Int y=(x/2);
    Int res=y*(y+1);
    if(x>y*2) res+=x/2+1;
    return res;
  };
  
  Int l=0,r=1e12;
  while(l+1<r){
    Int m=(l+r)>>1;
    if(calc(m)<=k) l=m;
    else r=m;
  }

  assert(calc(l)<=k);
  assert(calc(r)>k);

  Int a=l/2+1;
  k-=calc(l);
  //cout<<l<<" "<<calc(l)<<":"<<k<<" "<<a<<endl;
  
  const Int MOD = 1e9+7;
  if(k<(a+1)/2){
    cout<<fib(k*2,MOD)*fib(l-k*2,MOD)%MOD<<endl;
    return 0;
  }
  Int b=(a-k)*2-1;
  //cout<<b<<":"<<fib(b,MOD)<<endl;
  //cout<<l-b<<":"<<fib(l-b,MOD)<<endl;
  cout<<fib(b,MOD)*fib(l-b,MOD)%MOD<<endl;
  return 0;
}


```