2019計ニンニクの道初戦3 D.アリババがSARSの征戦に協力(困難)(大数取余+オラ降順)

アリババがSARSに協力

33.29%

 1000ms

 262144K

 
現在、SARSウイルスの研究は世界で行われており、科学者の研究によると、このウイルスとその変種DNAの1本の単鎖の中で、胞ピリジン、腺ピリジンはいずれもペアで現れていることが分かった.これは重大な発見であるが、このウイルスの最も主要な特徴ではない.この特徴は本当に弱いからだ.
このウイルスの特徴をさらに明らかにするために、CN疾病コントロールセンターとアリババグループは協力し、科学技術の力とプログラムの思考でこの難題を解決した.現在、アリババ特委はあなたをCN疾病コントロールセンターのSARS高級研究員に派遣し、この特徴の下で、SARSウイルスのDNA配列の個数になる可能性があることを研究しています.より正確には、次の条件を満たす長さnnの文字列の数をすべて統計する必要があります.

文字列は、A、T、C、Gのみからなる

である.

Aは偶数回(出現しなくてもよい)

が出現する.

Cは偶数回(現れなくてもよい)

が現れる.
n=2 n=2の場合、条件を満たすすべての文字列は以下の66個である.
TT,TG,GT,GG,AA,CC.
注:この数は非常に大きい可能性がありますので、10^9+7109+7の型取りの結果を与えるだけでいいです.
入力フォーマット
入力ファイルにはnnがいくつか与えられています.最後は数字00で終わる.
出力フォーマット
入力ファイルのnnごとに、条件を満たす文字列の個数対10^9+7109+7の型取りの結果が出力されます.
データ範囲
n\le 10^{(10^5)}n≤10(105)
サンプル入力コピー

1
2
3
100
0

サンプル出力コピー

2
6
20
113046907




  dfs       ：2^n+4^n
           ，            +    。
    HDU - 4704 sum     +    

#include
#define MOD 1000000007
using namespace std;
typedef long long ll;

char s[100005];

ll qMod(ll a,ll b){
    ll ans=1;
    a%=MOD;
    while(b){
        if(b&1) ans=ans*a%MOD;
        b>>=1;
        a=a*a%MOD;
    }
    return ans;
}
int main()
{
    int n,len,i;
    while(scanf(" %s",s)&&s[0]!='0'){
        ll c=0;
        len=strlen(s);
        for(i=0;i){
            int x=s[i]-'0';
            c=c*10+x;
            if(c>1000000006) c%=1000000006;
        }
        c=((c-1)%1000000006+1000000006)%1000000006;
        printf("%lld
",(qMod(2,c)+qMod(4,c))%MOD);
    }
    return 0;
}