1309 동물원

#include <stdio.h>
 
int arr[100005] = { 0 };
 
int main() {
    int n;
    scanf("%d", &n);
 
    arr[1] = 3;
    arr[2] = 7;
    for (int i = 3; i <= n; i++) {
        arr[i] = (arr[i - 1] * 2 + arr[i - 2]) % 9901;
    }
 
    printf("%d", arr[n]);
}