2100 問題 B: SARS病毒
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 98 解決: 41
題目描述
目前，SARS 病毒的研究在世界范圍內(nèi)進(jìn)行，經(jīng)科學(xué)家研究發(fā)現(xiàn)，該病毒及其變種的 DNA 的一條單鏈中，胞嘧啶、腺嘧啶均是成對(duì)出現(xiàn)的。
這雖然是一個(gè)重大發(fā)現(xiàn)，但還不是該病毒的最主要特征，因?yàn)檫@個(gè)特征實(shí)在太弱了。
為了進(jìn)一步搞清楚該病毒的特征，CN 疾病控制中心和阿里巴巴集團(tuán)合作，用科技的力量和程序的思維來解決這個(gè)難題。
現(xiàn)阿里巴巴特委派你成為 CN 疾病控制中心的 SARS 高級(jí)研究員，去研究在這個(gè)特征下，可能成為 SARS 病毒的 DNA 序列的個(gè)數(shù)。
更精確地說，你需要統(tǒng)計(jì)所有滿足下列條件的長度為 n 的字符串的個(gè)數(shù):
1、字符串僅由 A、T、C、G 組成
2、A 出現(xiàn)偶數(shù)次(也可以不出現(xiàn))
3、C 出現(xiàn)偶數(shù)次(也可以不出現(xiàn))
當(dāng) n=2 時(shí)，所有滿足條件的字符串有如下 6 個(gè):
TT，TG，GT，GG，AA，CC。
注： 由于這個(gè)數(shù)可能非常龐大，你只需給出對(duì) 10^9 + 7 取模的結(jié)果即可。
輸入
輸入文件給出了若干個(gè) n。最后以數(shù)字 0 結(jié)束。
輸出
對(duì)于輸入文件中的每一個(gè) n，輸出滿足條件的字符串的個(gè)數(shù)對(duì) 10^9 + 7 取模的結(jié)果。
數(shù)據(jù)范圍:
n≤1000
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情