11727번: 2xn 타일링 2

#include<cstdio>

long long tile[1001];

int main()

{

tile[1] = 1;

tile[2] = 3;

int n;

scanf("%d", &n);

for (int i = 3; i <= n; ++i)

tile[i] = (tile[i - 1] + 2 * tile[i - 2]) % 10007;

printf("%lld", tile[n]);

}