题目描述
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^n
n为奇数的时候，
易知没有可能有自身排列与倒转后相等的染色方案，所以方案数为2^(n-1)
n为偶数的时候
可能存在自身排列在倒转转色后与原排列的染色方案
以染红色为0，染白色为1，
1100 -》 倒转变色后 1100 就是一种
可以发现第一位与最后一位是10（或01）对应的，同理一直到n/2位，所以其实就在n/2里随意排列0，1
所以这样的染色方案共有2^(n/2)种
其他的染色方案在2^n都重复了两次
所有最终的结果就是2^(n/2) + （2^n - 2^(n/2）) / 2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long LL;
#define MOD 1000000007
LL Fast_Mod(LL a,LL b,LL p){
LL res = ,base = a;
while (b){
if (b&)
res = (res*base) % p;
base = (base*base) % p;
b = b >> ;
}
return res;
} LL n; int main(){
while (scanf("%lld",&n)!= EOF){
if (n % == ){
LL tmp1 = Fast_Mod(,n/,MOD) % MOD;
LL tmp2 = Fast_Mod(,n-,MOD) % MOD;
LL tmp3 = Fast_Mod(,n/-,MOD) % MOD;
LL res = (tmp1 + tmp2 - tmp3 + MOD) % MOD;
printf("%lld\n",res);
}
else
printf("%lld\n",Fast_Mod(,n-,MOD));
}
return ;
}