Language: C++

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
const ll mod = 1000000007;
struct Mod
{
	ll num;
	Mod() : num(0) { ; }
	Mod(ll n) : num(n % mod) { ; }
	operator ll() { return num; }
};


Mod operator+(Mod a, Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator-(Mod a, Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator*(Mod a, Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator+=(Mod &a, Mod b) { return a = a + b; }
Mod operator-=(Mod &a, Mod b) { return a = a - b; }
Mod operator^(Mod a, ll n)
{
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod inv(Mod a) { return a ^ (mod - 2); }
Mod operator/(Mod a, Mod b) { return a * inv(b); }

Mod fact(Mod n)
{
	if (n < 0) assert(false);
	if (n == 0 || n == 1) return 1;
	else return n*fact(n - (Mod)1);
}

Mod nPk(Mod n, Mod k)
{
	if (n < 0 || k < 0 || n < k) assert(false);
	return fact(n) / fact(k);
}

Mod nCk(Mod n, Mod k)
{
	if (n < 0 || k < 0 || n < k) assert(false);
	return nPk(n, k) / fact(n - k);
}

Mod nHk(Mod n, Mod k)
{
	if (n < 0 || k < 0 || n < k) assert(false);
	return nCk(n + k - (Mod)1, k);
}


typedef Mod Data;
typedef vector<Data> Array;
typedef vector<Array> Matrix;

bool is_zero(Data dat) { return (abs(dat) < EPS); }

Matrix operator-(Matrix mat) {
	REP(i, mat.size()) REP(j, mat[0].size()) mat[i][j] = -mat[i][j];
	return mat;
}

Matrix operator+(Matrix lhs, const Matrix &rhs) {
	REP(i, lhs.size()) REP(j, lhs[0].size()) lhs[i][j] = lhs[i][j] + rhs[i][j];
	return lhs;
}

Matrix operator-(Matrix lhs, const Matrix &rhs) {
	REP(i, lhs.size()) REP(j, lhs[0].size()) lhs[i][j] = lhs[i][j] - rhs[i][j];
	return lhs;
}

Matrix operator*(const Matrix &lhs, const Matrix &rhs) {
	Matrix res(lhs.size(), Array(rhs[0].size(), 0));
	REP(i, lhs.size()) REP(j, rhs[0].size()) REP(k, rhs.size())
		res[i][j] = fma(lhs[i][k], rhs[k][j], res[i][j]);
	return res;
}

Array operator+(const Array &lhs, const Array &rhs) {
	Array res = lhs;
	REP(i, rhs.size()) res[i] = res[i] + rhs[i];
	return res;
}

Array operator*(const Matrix &lhs, const Array &rhs) {
	Array res(lhs.size());
	REP(i, lhs.size())
		res[i] = inner_product(begin(lhs[i]), end(lhs[i]), begin(rhs), Data(0));
	return res;
}

Array operator*(Data scalar, const Array &rhs) {
	Array res(rhs.size());
	REP(i, rhs.size())
		res[i] = scalar * rhs[i];
	return res;
}

Matrix transpose(const Matrix &A) {
	const int n = A[0].size(), m = A.size();
	Matrix res(n, Array(m, 0));
	REP(i, n)REP(j, m) res[i][j] = A[j][i];
	return res;
}

Data inner_product_ex(const Array& a, const Array& b, const Matrix& m) {
	Array b_prime = m*b;
	return inner_product(begin(a), end(a), begin(b_prime), Data(0));
}

Data norm(const Array &a) {
	return inner_product(begin(a), end(a), begin(a), Data(0));
}

Data norm(const Array &a, const Matrix &M) {
	return inner_product_ex(a, a, M);
}

int rankMat(Matrix A) {
	const int n = A.size(), m = A[0].size();
	int r = 0;
	for (int i = 0; r < n && i < m; ++i) {
		int pivot = r;
		for (int j = r + 1; j < n; ++j)
			if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
		swap(A[pivot], A[r]);
		if (is_zero(A[r][i])) continue;
		for (int k = m - 1; k >= i; --k)
			A[r][k] = A[r][k] / A[r][i];
		for (int j = r + 1; j < n; ++j)
			for (int k = m - 1; k >= i; --k)
				A[j][k] = fma(-A[r][k], A[j][i], A[j][k]);
		++r;
	}
	return r;
}

Data det(Matrix A) {
	const int n = A.size();
	Data D = Data(1);
	for (int i = 0; i < n; ++i) {
		int pivot = i;
		for (int j = i + 1; j < n; ++j)
			if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
		swap(A[pivot], A[i]);
		D = D * A[i][i] * Data(i != pivot ? -1 : 1);
		if (is_zero(A[i][i])) break;
		for (int j = i + 1; j < n; ++j)
			for (int k = n - 1; k >= i; --k)
				A[j][k] = A[j][k] - A[i][k] * A[j][i] / A[i][i];
	}
	return D;
}

Matrix pow(Matrix x, ll n)
{
	Matrix res = { {1,0},{1,0} };
	while (n > 0)
	{
		if (n & 1) res = res * x;
		x = x*x;
		n >>= 1;
	}
	return res;
}


Mod fib(ll a)
{
	a++;
	Matrix mat = { {1,1},{1,0} };
	Array p = { 1,0 };
	Array q = pow(mat, a) * p;
	return q[0];
}

ll calc(ll a, ll b)
{
	return fib(a) * fib(b);
}


int main()
{
	cin.sync_with_stdio(false);
	ll k;
	cin >> k;
	if (k == 1)
	{
		puts("1");
		return 0;
	}
	ll lb = 0, ub = INF;
	while (ub - lb > 1)
	{
		ll mid = (lb + ub) / 2;
		if (mid % 2)
		{
			ll tmp = mid / 2 + 1;
			ll cnt = (1 + tmp)*tmp;
			if (cnt >= k) ub = mid;
			else lb = mid;
		}
		else
		{
			ll tmp = mid / 2;
			ll cnt = (1 + tmp)*tmp + tmp + 1;
			if (cnt >= k) ub = mid;
			else lb = mid;
		}
	}
	int tmp = (lb + 1) / 2;
	int cnt = (1 + tmp)*tmp;
	if (lb % 2 == 0) cnt += tmp + 1;
	int p = k - cnt - 1;
	int a;
	int len = ub / 2 + 1;
	if ((len + 1) / 2 > p) a = 2 * p;
	else a = (len - p - 1) * 2 + 1;
	cout << calc(ub - a, a) << endl;
	return 0;
}

Compiler output:
a.cc: In function 'Matrix operator*(const Matrix&, const Matrix&)':
a.cc:95:32: error: no matching function for call to 'fma(const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type&, const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type&, __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type&)'
   95 |                 res[i][j] = fma(lhs[i][k], rhs[k][j], res[i][j]);
      |                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/features.h:523,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/c++config.h:683,
                 from /usr/include/c++/14/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:33,
                 from a.cc:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:373:1: note: candidate: 'double fma(double, double, double)' (near match)
  373 | __MATHCALL (fma,, (_Mdouble_ __x, _Mdouble_ __y, _Mdouble_ __z));
      | ^~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:373:1: note:   conversion of argument 2 would be ill-formed:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:373:1: error: invalid user-defined conversion from 'const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type' {aka 'const Mod'} to 'double' [-fpermissive]
a.cc:26:9: note: candidate is: 'Mod::operator ll()' (near match)
   26 |         operator ll() { return num; }
      |         ^~~~~~~~
a.cc:26:9: note:   passing 'const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type*' {aka 'const Mod*'} as 'this' argument discards qualifiers
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:373:1: error: passing 'const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type' {aka 'const Mod'} as 'this' argument discards qualifiers [-fpermissive]
  373 | __MATHCALL (fma,, (_Mdouble_ __x, _Mdouble_ __y, _Mdouble_ __z));
      | ^~~~~~~~~~
a.cc:26:9: note:   in call to 'Mod::operator ll()'
   26 |         operator ll() { return num; }
      |         ^~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:114:
/usr/include/c++/14/cmath:2403:3: note: candidate: 'constexpr long double std::fma(long double, long double, long double)' (near match)
 2403 |   fma(long double __x, long double __y, long double __z)
      |   ^~~
/usr/include/c++/14/cmath:2403:3: note:   conversion of argument 2 would be ill-formed:
/usr/include/c++/14/cmath:2403:3: error: invalid user-defined conversion from 'const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type' {aka 'const Mod'} to 'long double' [-fpermissive]
a.cc:26:9: note: candidate is: 'Mod::operator ll()' (near match)
   26 |         operator ll() { return num; }
      |         ^~~~~~~~
a.cc:26:9: note:   passing 'const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type*' {aka 'const Mod*'} as 'this' argument discards qualifiers
/usr/include/c++/14/cmath:2403:3: error: passing 'const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type' {aka 'const Mod'} as 'this' argument discards qualifiers [-fpermissive]
 2403 |   fma(long double __x, long double __y, long double __z)
      |   ^~~
a.cc:26:9: note:   in call to 'Mod::operator ll()'
   26 |         operator ll() { return num; }
      |         ^~~~~~~~
/usr/include/c++/14/cmath:2399:3: note: candidate: 'constexpr float std::fma(float, float, float)' (near match)
 2399 |   fma(float __x, float __y, float __z)
      |   ^~~
/usr/include/c++/14/cmath:2399:3: note:   conversion of argument 2 would be ill-formed:
/usr/include/c++/14/cmath:2399:3: error: invalid user-defined conversion from 'const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type' {aka 'const Mod'} to 'float' [-fpermissive]
a.cc:26:9: note: candidate is: 'Mod::operator ll()' (near match)
   26 |         operator ll() { return num; }
      |         ^~~~~~~~
a.cc:26:9: note:   passing 'const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type*' {aka 'const Mod*'} as 'this' argument discards qualifiers
/usr/include/c++/14/cmath:2399:3: error: passing 'const __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type' {aka 'const Mod'} as 'this' argument discards qualifiers [-fpermissive]
 2399 |   fma(float __x, float __y, float __z)
      |   ^~~
a.cc:26:9: note:   in call to 'Mod::operator ll()'
   26 |         operator ll() { return num; }
      |         ^~~~~~~~
/usr/include/c++/14/cmath:3748:5: note: candidate: 'template<class _Tp, class _Up, class _Vp> constexpr typename __gnu_cxx::__promote_3<_Tp, _Up, _Vp>::__type std::fma(_Tp, _Up, _Vp)'
 3748 |     fma(_Tp __x, _Up __y, _Vp __z)
      |     ^~~
/usr/include/c++/14/cmath:3748:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/14/bits/stl_algobase.h:62,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/ext/type_traits.h: In substitution of 'template<class _Tp, class _Up, class _Vp> using __gnu_cxx::__promote_3 = __gnu_cxx::__promote<decltype (((typename __gnu_cxx::__promote<_Tp, std::__is_integer<_Tp>::__value>::__type)(0) + ((typename __gnu_cxx::__promote<_Up, std::__is_integer<_Up>::__value>::__type)(0) + (typename __gnu_cxx::__promote<_Vp, std::__is_integer<_Vp>::__value>::__type)(0))))> [with _Tp = Mod; _Up = Mod; _Vp = Mod]':
/usr/include/c++/14/cmath:3748:5:   required by substitution of 'template<class _Tp, class _Up, class _Vp> constexpr typename __gnu_cxx::__promote_3<_Tp, _Up, _Vp>::__type std::fma(_Tp, _Up, _Vp) [with _Tp = Mod; _Up = Mod; _Vp = Mod]'
a.cc:95:18:   required from here
   95 |                 res[i][j] = fma(lhs[i][k], rhs[k][j], res[i][j]);
      |                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/ext/type_traits.h:226:61: error: no type named '__type' in 'struct __gnu_cxx::__promote<Mod, false>'
  226 |     using __promoted_t = decltype((typename __promote<_Tp>::__type(0) + ...));
      |                                                             ^~~~~~~~~
/usr/include/c++/14/ext/type_traits.h:226:61: error: no type named '__type' in 'struct __gnu_cxx::__promote<Mod, false>'
/usr/include/c++/14/ext/type_traits.h:226:61: error: no type named '__type' in 'struct __gnu_cxx::__promote<Mod, false>'
a.cc: In function 'int rankMat(Matrix)':
a.cc:152:46: error: call of overloaded 'fma(ll, __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type&, __gnu_cxx::__alloc_traits<std::allocator<Mod>, Mod>::value_type&)' is ambiguous
  152 |                                 A[j][k] = fma(-A[r][k], A[j][i], A[j][k]);
      |                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:373:1: note: candidate: 'double fma(double, double, double)'
  373 | __MATHCALL (fma,, (_Mdouble_ __x, _Mdouble_ __y, _Mdouble_ __z));
      | ^~~~~~~~~~
/usr/include/c++/14/cmath:2403:3: note: candidate: 'constexpr long double std::fma(long double, long double, long double)'
 2403 |   fma(long double __x, long double __y, long double __z)
      |   ^~~
/usr/include/c++/14/cmath:2399:3: note: candidate: 'constexpr float std::fma(float, float, float)'
 2399 |   fma(float __x, float __y, float __z)
      |   ^~~