[백준]1904-01타일(설명X)

//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
int fib(int n);
 
int main() {
    int N;
    cin >> N;
    cout << fib(N + 1) << endl;
}
 
int fib(int n) {
    if (n < 3)
        return 1;
 
    long num1 = 1, num2 = 1, num3 = 0;
    for (int i = 3; i <= n; i++) {
        num3 = (num1 + num2) % 15746;
        num1 = num2;
        num2 = num3;
    }
    return num3;
}