HDU 2154 跳舞毯

#include <bits/stdc++.h>
using namespace std;

int a[1111];

int main() {
    a[1] = 0, a[2] = 2, a[3] = 2, a[4] = 6;
    for(int i = 5; i <=1001; i ++)
        a[i] = (a[i - 1] + 2 * a[i - 2]) % 10000;
    
    int N;
    while(~scanf("%d", &N)) {
        if(N == 0) break;
        printf("%d\n", a[N]);
    }
    return 0;
}