#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)
#include <vector>
#include <iostream>
using namespace std;

template <class T> struct Matrix {
  vector<vector<T>> value;
  T init;

  Matrix(vector<vector<T>> vec,T init_) :init(init_), value(vec) {}
  Matrix(int h, int w, T init_) : init(init_) , value(h, vector<T>(w,init_)) {}

  Matrix<T> operator*(Matrix<T>& left) {
      Matrix<T> res(value.size(),left[0].size(),init);
      for(int i = 0;i < value.size();i++){
          for(int k = 0;k < left.size();k++){
              for(int j = 0;j < left[0].size();j++){
                  res[i][j] = (res[i][j] + value[i][k] * left[k][j]);
              }
          }
      }
      return res;
  }

  Matrix<T> operator+(Matrix<T>& left){
      Matrix<T> res = *this;
      for(int i = 0;i < res.size();i++){
          for(int j = 0;j < res[0].size();j++){
              res[i][j] += left[i][j];
          }
      }
      return res;
  }

  Matrix<T> operator*(T c){
      Matrix<T> res = *this;
      for(int i = 0;i < res.size();i++){
          for(int j = 0;j < res[0].size();j++){
              res[i][j] *= c;
          }
      }
      return res;
  }

  vector<T>& operator[](int n){
      return value[n];
  }

  size_t size(){
      return value.size();
  }

  Matrix<T> operator^(long long n){
      Matrix<T> a = *this;
      Matrix<T> res(a.size(),a.size(),init);
      for(int i = 0;i < a.size();i++){
          res[i][i] = 1;
      }

      while(n > 0){
          if(n & 1) res = res * a;
          a = a * a;
          n >>= 1;
      }
      return res;
  }
};
template <i64 MOD> struct ModInt {
  i64 value;

  ModInt(i64 v = 0) { value = v % MOD; }

  operator i64() { return value; }
  ModInt<MOD> operator+(int v) { return (value + v) % MOD; }
  ModInt<MOD> operator+(i64 v) { return (value + v) % MOD; }

  ModInt<MOD> operator-(i64 v) {
    v %= MOD;
    return (MOD + value - v) % MOD;
  }

  ModInt<MOD> operator*(i64 v) { return (value * v) % MOD; }
};



i64 k;

int main(){
    cin >> k;
    i64 len;
    {
        i64 ok = 0;
        i64 ng = 1e10;
        while(ng - ok > 1){
            i64 mid = (ok + ng) / 2;
            i64 t = (mid / 2 - 1) * ((mid / 2));
            if(mid % 2 == 1) t += (mid - 1) / 2;
            if(t < k) ok = mid;
            else ng = mid;
        }
        len = ok;
    }
    i64 t = (len / 2 - 1) * ((len / 2));
    if (len % 2 == 1)
        t += (len - 1) / 2;
    k -= t + 1;


    i64 x = 0;
    i64 y = 0;
    i64 half = len / 4;

    if(k * 2 + 1 <= len / 2){
        x = k * 2 + 1;
        y = len - x;
    }
    else{
        k = len / 2 - k;
        x = 2 * k;
        y = len - x;
    }
    const i64 MOD = 1e9 + 7;
    using mint = ModInt<MOD>;

    auto mat = Matrix<mint>({{1,1},{1,0}},0);
    cout << (mat ^ (x + 1))[1][0] * (mat ^ (y + 1))[1][0] << endl;
}

### Prompt

Generate a Cpp solution to the following problem:

Example

Input

5


Output

5

### Response

```cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)
#include <vector>
#include <iostream>
using namespace std;

template <class T> struct Matrix {
  vector<vector<T>> value;
  T init;

  Matrix(vector<vector<T>> vec,T init_) :init(init_), value(vec) {}
  Matrix(int h, int w, T init_) : init(init_) , value(h, vector<T>(w,init_)) {}

  Matrix<T> operator*(Matrix<T>& left) {
      Matrix<T> res(value.size(),left[0].size(),init);
      for(int i = 0;i < value.size();i++){
          for(int k = 0;k < left.size();k++){
              for(int j = 0;j < left[0].size();j++){
                  res[i][j] = (res[i][j] + value[i][k] * left[k][j]);
              }
          }
      }
      return res;
  }

  Matrix<T> operator+(Matrix<T>& left){
      Matrix<T> res = *this;
      for(int i = 0;i < res.size();i++){
          for(int j = 0;j < res[0].size();j++){
              res[i][j] += left[i][j];
          }
      }
      return res;
  }

  Matrix<T> operator*(T c){
      Matrix<T> res = *this;
      for(int i = 0;i < res.size();i++){
          for(int j = 0;j < res[0].size();j++){
              res[i][j] *= c;
          }
      }
      return res;
  }

  vector<T>& operator[](int n){
      return value[n];
  }

  size_t size(){
      return value.size();
  }

  Matrix<T> operator^(long long n){
      Matrix<T> a = *this;
      Matrix<T> res(a.size(),a.size(),init);
      for(int i = 0;i < a.size();i++){
          res[i][i] = 1;
      }

      while(n > 0){
          if(n & 1) res = res * a;
          a = a * a;
          n >>= 1;
      }
      return res;
  }
};
template <i64 MOD> struct ModInt {
  i64 value;

  ModInt(i64 v = 0) { value = v % MOD; }

  operator i64() { return value; }
  ModInt<MOD> operator+(int v) { return (value + v) % MOD; }
  ModInt<MOD> operator+(i64 v) { return (value + v) % MOD; }

  ModInt<MOD> operator-(i64 v) {
    v %= MOD;
    return (MOD + value - v) % MOD;
  }

  ModInt<MOD> operator*(i64 v) { return (value * v) % MOD; }
};



i64 k;

int main(){
    cin >> k;
    i64 len;
    {
        i64 ok = 0;
        i64 ng = 1e10;
        while(ng - ok > 1){
            i64 mid = (ok + ng) / 2;
            i64 t = (mid / 2 - 1) * ((mid / 2));
            if(mid % 2 == 1) t += (mid - 1) / 2;
            if(t < k) ok = mid;
            else ng = mid;
        }
        len = ok;
    }
    i64 t = (len / 2 - 1) * ((len / 2));
    if (len % 2 == 1)
        t += (len - 1) / 2;
    k -= t + 1;


    i64 x = 0;
    i64 y = 0;
    i64 half = len / 4;

    if(k * 2 + 1 <= len / 2){
        x = k * 2 + 1;
        y = len - x;
    }
    else{
        k = len / 2 - k;
        x = 2 * k;
        y = len - x;
    }
    const i64 MOD = 1e9 + 7;
    using mint = ModInt<MOD>;

    auto mat = Matrix<mint>({{1,1},{1,0}},0);
    cout << (mat ^ (x + 1))[1][0] * (mat ^ (y + 1))[1][0] << endl;
}

```