[실1] 1309 - 동물원

#include <iostream>

int D[100001]={1,3};

int main()
{
    int N;
    std::cin>>N;
    
    for(int i=2;i<=N;i++)
        D[i]=(D[i-1]*2+D[i-2])%9901;
        
    std::cout<<D[N];
    
    return 0;
}