根据OEIS A192008中的公式有
$$T(n)=\sum (m+k+1)!\cdot \binom{m+k}{m} \cdot 2^k \cdot (k+v_1+v_2)! \cdot (m+k)!,$$
其中$v_1,v_2$分别各自取0和1（即一共四种情况），m和k取遍所有满足$2m+3k=n-1-v_1-v_2$的值。
令$h=v_1+v_2$，分别取$h=0,1,2$，用欧几里得法求出对应的m和k，再汇总（其中$h=1$的情况需要计入两次）即可得结果$44855254$。
mod=10**8+7
n=1000000
fac=[1,1]
inv=[0,1]
finv=[1,1]
pw2=[1,2]
for i in range(2,n+1):
fac.append((fac[-1]*i)%mod)
inv.append((mod-mod/i)*inv[mod%i]%mod)
finv.append((finv[-1]*inv[-1])%mod)
pw2.append((pw2[-1]*2)%mod)
C=lambda n,k:fac[n]*finv[n-k]%mod*finv[k]%mod
r=0
for h in (0,1,1,2):
k=0
while 3*k<=n-1-h:
m=n-1-h-3*k
if m%2==0:
m/=2
r=(r+fac[m+k+1]*C(m+k,m)%mod*pw2[k]%mod*fac[k+h]%mod*fac[k+m])%mod
k+=1
print r
|
