ソースコード
#include <bits/stdc++.h>
using namespace std;
template<int mod> struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; }
ModInt &operator-=(const ModInt &p) { if((x += mod-p.x) >= mod) x -= mod; return *this; }
ModInt &operator*=(const ModInt &p) { x = (int)(1LL*x*p.x%mod); return *this; }
ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; }
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const{
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
return ModInt(u);
}
ModInt pow(int e){
long long a = 1, p = x;
while(e > 0) {
if(e%2 == 0) {p = (p*p) % mod; e /= 2;}
else {a = (a*p) % mod; e--;}
}
return ModInt(a);
}
friend ostream &operator<<(ostream &os, const ModInt<mod> &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt<mod> &a) {
long long x;
is >> x;
a = ModInt<mod>(x);
return (is);
}
};
int main() {
constexpr int MOD = 1'000'000'007;
int q;
cin >> q;
ModInt<MOD> res = 1;
vector<ModInt<MOD>> a(100100);
a[0] = a[1] = 1;
for (int i = 2; i < q; i++) { a[i] = a[i-1] + a[i-2]; res *= a[i]; }
cout << res << endl;
return 0;
}