大意：给你一个整数N，代表字符串长度，每个位置上的字符可以是’C’ 或者 ‘P’，长度为N的字符串中有2^N种，为这些字符串中，包含几个‘CCPC’（一个字符串中的有贡献的ccpc要求不重叠）
思路：
长度为N，
包含一个‘CCPC’：
空的位置数是N-4，每个位置可以填两种字符，由插空法可知‘ccpc’有（N-4 +1）种插法，则共有2^(N-4) *（N-4 +1）种
包含两个‘CCPC’：
与上同理
共有2^(N-7) *（N-7 +1）种
包含…
但是注意!!!
ccpc . . . .
. . . . ccpc
第一个字符串填成ccpcccpc
第二个字符串填成ccpcccpc时，这是构成了同一种字符串，但是 两种ccpc的位置不同，所以在算的时候会算重，这就用到了容斥定理
所以总的答案=包含一个‘ccpc’的种数 - 包含两个个‘ccpc’的种数 + 包含三个‘ccpc’的种数 - 包含四个‘ccpc’的种数 …
例：
当 N=10时
总的答案=（6 +1）* 2 ^ 6 - （3 +1）* 2 ^ 3 + （0+1）* 2 ^ 0
我们把相加的项放一起，相减的项放一起，分开算
ans = （6 +1）* 2 ^ 6 + （0+1）* 2 ^ 0 （最小空位数是0，有两项）
ans2 = （3 +1）* 2 ^ 3 （最小空位数是3，有一项）
答案= ans - ans2
最终式子的化简如下（错位相减法）：
（N=10，ans的m=0，n=2 ， ans2的m=3，n=1）
代码实现时别忘了取模+逆元
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#pragma warning(disable:4996)
#define inr register int
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const int maxn = 200007;//1e5+7
const ll mod = 1000000007;//1e9+7
ll ksm(ll x, ll y)
{
ll ans = 1;
x = x % mod;
while (y > 0)
{
if (y & 1) ans = (ans * x) % mod;
y >>= 1;
x = (x * x) % mod;
}
return ans%mod;
}
ll inv(ll x)
{
return ksm(x, mod - 2);
}
int main()
{
ios;
int T;
ll n;
cin >> T;
while (T--)
{
cin >> n;
if(n<4)cout<<0<<endl;
else
{
ll m = (n - 4ll) % 6;
ll N = (n - 4ll) / 6+1;
// cout<<N<<" "<<m<<endl;
ll ans = (((m + 1)%mod * ksm(2, m) % mod)%mod + (6ll * ksm(2, m + 6) % mod * (ksm(2, 6ll*N-6) - 1 + mod) % mod * inv(63) % mod)%mod-(((m+6ll*N-5))%mod*ksm(2,m+6*N)%mod)%mod+mod) % mod;
ll fm = (-63 + mod) % mod;
fm = inv(fm);
ans = ans * fm % mod;
// cout<<ans<<endl;
ll ans2=0;
if(n>=7)
{
m = (n - 7ll) % 6;
N = (n - 7ll) / 6+1;
ans2 = (((m + 1)%mod * ksm(2, m) % mod)%mod + (6ll * ksm(2, m + 6) % mod * (ksm(2, 6ll*N-6) - 1 + mod) % mod * inv(63) % mod)%mod-(((m+6ll*N-5))%mod*ksm(2,m+6*N)%mod)%mod+mod) % mod;
fm = (-63 + mod) % mod;
fm = inv(fm);
ans2 = ans2 * fm % mod;
}
cout << (ans - ans2 + mod) % mod << endl;
}
}
return 0;
}