https://www.acmicpc.net/problem/1904
#include <iostream>
using namespace std;
int dp[1000001] = { 0 };
int main(void)
{
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
int N;
cin >> N;
for (int i = 4; i <= N; i++)
{
dp[i] = (dp[i - 1]%15746 + dp[i - 2]%15746)%15746;
}
cout << dp[N];
return 0;
}