1563 개근상

#include <stdio.h>
 
long long dp[1005][3][4] = { 0 };
 
int main() {
    int n;
    scanf("%d", &n);
 
    dp[1][0][0] = 1;
    dp[1][1][0] = 1;
    dp[1][0][1] = 1;
 
    long long rst = 0;
    for (int i = 2; i <= n; i++) {
        dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2])%1000000;
        dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]
                            + dp[i-1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2])%1000000;
        
        dp[i][0][1] = dp[i - 1][0][0]%1000000;
        dp[i][1][1] = dp[i - 1][1][0]%1000000;
 
        dp[i][0][2] = dp[i - 1][0][1]%1000000;
        dp[i][1][2] = dp[i - 1][1][1]%1000000;
 
        if (i == n) {
            for (int k = 0; k <= 1; k++) {
                for (int t = 0; t <= 2; t++) {
                    rst += dp[i][k][t];
                }
            }
        }
    }
 
    printf("%lld", rst%1000000);
}