[#1904] 01타일

#include <iostream>
#include <vector>
#define MOD 15746
 
using namespace std;
 
vector<int> dp(1000001, -1);
 
int findAnswer(int n) {
    if (n <= 2) {
        return n;
    }
 
    int& ret = dp[n];
 
    if (ret != -1) return ret;
 
    int a = findAnswer(n - 2);
    int b = findAnswer(n - 1);
    return ret = (a + b) % MOD;
}
 
int main() {
    int n;
    dp[1] = 1;
    dp[2] = 2;
 
    cin >> n;
 
    cout << findAnswer(n) << endl;;
 
    return 0;
}