ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int mod = 1e9 + 7;
inline int64 modPow(int64 x, int64 n)
{
if(n == 0) return (1);
int64 ret = modPow(x, n / 2);
(ret *= ret) %= mod;
if(n & 1) (ret *= x) %= mod;
return (ret);
}
inline int64 modInv(int64 a)
{
return (modPow(a, mod - 2));
}
int dp[100001];
int64 rec(int idx)
{
if(idx <= 0) return (1);
if(~dp[idx]) return (dp[idx]);
return (dp[idx] = (rec(idx - 2) * rec(idx - 1) % mod * modInv(rec(idx - 3)) % mod + rec(idx - 1) * rec(idx - 1) % mod * modInv(rec(idx - 2)) % mod) % mod);
}
int main()
{
int N;
cin >> N;
memset(dp, -1, sizeof(dp));
cout << rec(N - 2) << endl;
}