提示: 欢迎访问OurACM平台。
Problem 2198 快来快来数一数

Accept: 219    Submit: 706
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

n个六边形排成一行,相邻两个六边形共用一条边,如下图所示:

记这个图形的生成树个数为t(n)(由于每条边都是不同的,不存在同构的问题)。那么t(1)=6,t(2)=35……

给出n,求mod 1000000007

Input

第一行给出数据组数T。

之后每一行给出一个正整数n。

T大约为50000,n<=10^18。

Output

每组数据输出一行答案。

Sample Input

2 2 12345678987654321

Sample Output

41 733521876

Source

FOJ有奖月赛-2015年10月

Submit  Back  Status  Discuss