主页 讨论版 问题 名次 状态 统计
12月将举办首届西电ACM新生赛,敬请期待~~~~
问题 C: Chemistry Problem

问题 C: Chemistry Problem

时间限制: 1 Sec  内存限制: 128 MB
提交: 86  解决: 33
[提交][状态][讨论版]

题目描述

lw最近正在学习立体化学。立体化学中常用Fischer投影式表示分子的立体构型,例如,对于酒石酸HOOC(CHOH)2COOH,如果用一根横线表示羟基,略去氢原子,它有22=4种可能的Fischer投影式,如图所示。

然而,酒石酸的立体异构体数目并不是4,因为Fischer投影式具有一个奇怪的性质:将其在纸面上旋转180度后,仍然表示一个相同的立体异构体。例如,上图中第0和第3个(从左往右数,编号从0开始)Fischer投影式其实表示同一种立体异构体。

那么问题来了:对于糖酸HOOC(CHOH)nCOOH,它有多少不同的立体异构体呢?


更形式化地,本题就是:用2种颜色对排成一排的n个方块染色,将所有方块的顺序颜色都反转,得到的染色方案与原染色方式视为等价的,那么有多少种不同的染色方案?

由于答案很大,而且lw很讨厌高精度,你只要输出答案对1000000007的模即可。

输入

多组数据(最多1000组)。每组数据1行,包含整数n。

输入保证:1<=n<=109

输出

对于每组数据,输出1行,包含1个整数,即答案模1000000007。

样例输入

2
3

样例输出

3
4

提示

[提交][状态][讨论版]