Baekjoon algorithm 1904

#include <cstdio>
using namespace std;

const int max = 1000000;
int n;
int cnt[max];

int main() {
	int i;
	scanf("%d", &n);
	cnt[0] = 0;
	cnt[1] = 1;
	cnt[2] = 2;

	for (i = 3; i <= n; i++) {
		cnt[i] = (cnt[i - 1] + cnt[i - 2]) % 15746;
	}

	printf("%d", cnt[n]);
	return 0;
}