Dotcpp  >  编程题库  >  SARS病毒
题目 2100:

SARS病毒

时间限制: 2s 内存限制: 192MB 提交: 97 解决: 40

题目描述

目前,SARS 病毒的研究在世界范围内进行,经科学家研究发现,该病毒及其变种的 DNA 的一条单链中,胞嘧啶、腺嘧啶均是成对出现的。

这虽然是一个重大发现,但还不是该病毒的最主要特征,因为这个特征实在太弱了。

为了进一步搞清楚该病毒的特征,CN 疾病控制中心和阿里巴巴集团合作,用科技的力量和程序的思维来解决这个难题。

现阿里巴巴特委派你成为 CN 疾病控制中心的 SARS 高级研究员,去研究在这个特征下,可能成为 SARS 病毒的 DNA 序列的个数。

更精确地说,你需要统计所有满足下列条件的长度为 n 的字符串的个数:

    1、字符串仅由 A、T、C、G 组成
    2、A 出现偶数次(也可以不出现)
    3、C 出现偶数次(也可以不出现)

当 n=2 时,所有满足条件的字符串有如下 6 个:

TT,TG,GT,GG,AA,CC。

注: 由于这个数可能非常庞大,你只需给出对 10^9 + 7 取模的结果即可。

输入格式

输入文件给出了若干个 n。最后以数字 0 结束。

输出格式

对于输入文件中的每一个 n,输出满足条件的字符串的个数对 10^9 + 7 取模的结果。


数据范围:
n≤1000

样例输入

1
2
3
100
0

样例输出

2
6
20
113046907

提示

零基础同学可以先学习视频课程,包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程,提供视频讲解以及配套习题,还有老师答疑,点击这里了解课程详情
标签