백준 1904

#include <iostream>
#include <algorithm>
#include <vector>



using namespace std;

int num;

long long arr[1000000];


int main(void)
{

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> num;

    arr[0] = 1;
    arr[1] = 2;

    for (int i = 2; i < num; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) %15746;
    }

    cout << arr[num - 1];


}