奇怪的DNA序列

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

小鱼干吃货课堂开课了,前排马扎瓜子准备好,我们先来看看什么是碱基:

 

 

 

 

     碱基是指嘌呤和嘧啶的衍生物,是核酸、核苷、核苷酸的成分。DNA和RNA的主要碱基略有不同,其重要区别是:胸腺嘧啶是DNA的主要嘧啶碱,在RNA中极少见;相反,尿嘧啶是RNA的主要嘧啶碱,在DNA中则是稀有的。

 

     除主要碱基外,核酸中也有一些含量很少的稀有碱基。稀有碱基的结构多种多样,多半是主要碱基的甲基衍生物。tRNA往往含有较多的稀有碱基,有的tRNA含有的稀有碱基达到10%。嘌呤和嘧啶碱基是近乎平面的分子,相对难溶于水:在约260纳米的紫外光区有较强的吸收。

 

     在脱氧核糖核酸和核糖核酸中,起配对作用的部分是含氮碱基。5种碱基都是杂环化合物,氮原子位于环上或取代氨基上,其中一部分(取代氨基,以及嘌呤环的1位氮、嘧啶环的3位氮)直接参与碱基配对。碱基共有5种:胞嘧啶(缩写作C)、鸟嘌呤(G)、腺嘌呤(A)、胸腺嘧啶(T,DNA专有)和尿嘧啶(U,RNA专有)。顾名思义,5种碱基中,腺嘌呤和鸟嘌呤属于嘌呤族(缩写作R),它们具有双环结构。胞嘧啶、尿嘧啶、胸腺嘧啶属于嘧啶族(Y),它们的环系是一个六元杂环。RNA中,尿嘧啶取代了胸腺嘧啶的位置,值得注意的是,胸腺嘧啶比尿嘧啶多一个5位甲基,这个甲基增大了遗传的准确性。

 

     DNA(脱氧核糖核酸)的结构出奇的简单。DNA分子由两条很长的糖链结构构成骨架,通过碱基对结合在一起,就象梯子一样。整个分子环绕自身中轴形成一个双螺旋。两条链的空间是一定的,为2nm。在形成稳定螺旋结构的碱基对中共有4种不同碱基。根据它们英文名称的首字母分别称之为A(ADENINE 腺嘌呤)、T(THYMINE 胸腺嘧啶)、C(CYTOSINE 胞嘧啶)、G(GUANINE 鸟嘌呤),另有U(URACIL尿嘧啶)。DNA与RNA共有的碱基是腺嘌呤、胞嘧啶和鸟嘌呤。胸腺嘧啶存在于DNA中,而尿嘧啶则存在于RNA中。每种碱基分别与另一种碱基的化学性质完全互补,嘌呤是双环,嘧啶是单环,两个嘧啶之间空间太大,而嘌呤之间空间不够。这样A总与T配对,G总与C配对。这四种化学“字母”沿DNA骨架排列。“字母”(碱基)的一种独特顺序就构成一个“词”(基因)。每个基因有几百甚至几万个碱基对。

 

     碱基通过共价键与核糖或脱氧核糖的1位碳原子相连而形成的化合物叫核苷。核苷再与磷酸结合就形成核苷酸,磷酸基接在五碳糖的5位碳原子上。

 

     碱基还构成一些生命必须物质或是重要的辅酶,如ATP,GTP,CoA等,对生命活动的作用非常大。

 

 

 

——以上信息摘自“百度百科”,且并没什么卵用。

 

 

     好了说正事,话说现代医学高度发达,小鱼干作为业界最具权威的遗传学研究者,最近在某种奇怪的生物身上发现了一段奇怪的DNA序列,这段DNA序列长度固定,而且是单链DNA,但是同类生物间这段DNA序列的排列却是大不相同的,但也有规律可循,就是这段DNA序列的C(胞嘧啶)、T(胸腺嘧啶)碱基出现总次数均为偶数次,现在小鱼干想知道在这种情况下该生物在该段DNA序列上所有可能表现出的序列的种类数量。砖家的科研需要你的帮助。

Input

多组输入(挺多的)。

每组数据输入一个整数n(1<=n<2^31),表示该段DNA序列的长度。

Output

每组输出占一行,代表该生物这段DNA序列所有可能表现出的序列的种类数。由于结果可能会非常大,需要对1000000007取余。

Sample Input

1
2

Sample Output

2
6

Hint

由百科可知(其实是有用的2333),DNA序列仅胞嘧啶(C),鸟嘌呤(G),腺嘌呤(A),胸腺嘧啶(T)四种核苷酸组成,而C、T成对出现,所以当n=2时,所有可能的DNA序列为CC、GG、AA、TT、AG、GA。

Source

2016暑假集训结训赛 by Shannon