2013_12_CSP_4

#include <iostream>
#include <algorithm>
using namespace std;

long long arrays[1001][2][2][2] = {0};//存储整数位数与各数字出现与否的布尔值

void funny(int n, bool flag_0, bool flag_1, bool flag_3)//n是整数位数,flag表示对应数字不出现
{
    int res = 3 - (int)flag_0 - (int)flag_1 - (int)flag_3;//需要出现的数字个数
    if(flag_0 && flag_1 && flag_3) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = 1;//0,1,3 均不出现只能是2，只有一种情况
    else if((flag_0)&&(!flag_1)) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = 0;//如果0不需要出现而1需要则不存在
    else if(n < res) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = 0;//若不能使所有数字出现则不存在
    else if(n == res) //若刚好可使所有位数出现
    {
            if(flag_1) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = n;//如果1不需要出现则只有n种情况
            else if(flag_3) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = 1;//如果3不需要出现只有1种情况
            else arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = 3;//所有flag都需要出现过则有3种情况
    }
    else //若足够可使所有位数出现
    {
        if((flag_0)&&(flag_1)&&(!flag_3)) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = arrays[n-1][1][1][0] + arrays[n-1][1][1][1]; //只需要出现2与3
        if((!flag_0)&&(flag_1)&&(flag_3)) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = 2 * arrays[n-1][0][1][1] + arrays[n-1][1][1][1];//只需要出现2与0
        if((!flag_0)&&(flag_1)&&(!flag_3)) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = 2 * arrays[n-1][0][1][0] + arrays[n-1][1][1][0] + arrays[n-1][0][1][1];//需要出现2、0、3
        if((!flag_0)&&(!flag_1)&&(flag_3)) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = 2 * arrays[n-1][0][0][1] + arrays[n-1][0][1][1];//需要出现2、0、1                       //
        if((!flag_0)&&(!flag_1)&&(!flag_3)) arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] = 2 * arrays[n-1][0][0][0] + arrays[n-1][0][0][1] + arrays[n-1][0][1][0];//需要出现2、0、1、3
    }
    arrays[n][(int)flag_0][(int)flag_1][(int)flag_3] %= 1000000007;//余数处理
}

int main()
{
    int n;//输入的正整数
    cin >> n;
    n--;//首位必为2，故不考虑首位
    for(int i=1;i<=n-1;i++)
    {
        funny(i, true, true, true);
        funny(i, true, true, false);
        //funny(i, true, false, true);该情况不成立
        //funny(i, true, false, false);该情况不成立
        funny(i, false, true, true);
        funny(i, false, true, false);
        funny(i, false, false, true);
        funny(i, false, false, false);
    }
    funny(n, false, false, false);//更新n位数的情况
    cout << arrays[n][0][0][0] << endl;
    return 0;
}