简单dp问题，dp[i]代表前i天有多少种方案，分两种情况：

1、第i天的饭菜与第i-2天的饭菜不同，那么前i天有dp[i-2]*2种方案

2、第i天的饭菜与第i-1天的饭菜不同，那么前i天有dp[i-1]*2种方案

因此前i天共计dp[i-1]*2+dp[i-2]*2,在这中包含都不同的情况

#include <bits/stdc++.h>
#define size 100100
const int MOD=1e9+7;
using namespace std;
long long dp[size],n,m;
int main(){
    dp[1]=3,dp[2]=9;
    for (int i=3;i<size;i++){
        dp[i]=(dp[i-1]*2%MOD+dp[i-2]*2%MOD)%MOD;
    }
    scanf("%lld",&m);
    while (m--){
        scanf("%lld",&n);
        printf("%lld\n",dp[n]);
    }
    system("pause");
    return 0;
}