Ackerman

Time Limit
1s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
55.56%(5/9)
Description:



众所周知,当一个函数及它的一个变量是由函数自身定义时,称这个函数是双递归函数。当两个连续函数都趋于无穷时,我们常用洛必达法则来比较它们趋向无穷的快慢。函数的阶越高,它趋向无穷的速度就越快。在定义在正整数域上的函数中,n!趋向于正无穷的速度非常快,所以在算法设计中如果出现这样的时间复杂度就太糟糕了。

并非一切的递归函数都有通项公式Ackerman函数就是这么一个例子。它是一个双递归函数 Ackerman函数有A(n,m)有两个独立的整变量,其定义如下:


小S是特别聪明的,他发现了关于A(m, 3)的闭合表达式,其中2的层数为m.

但是小S最近忙着去各大公司面试,所以请你帮他求出A(m, 3)的值。




Input:

输入包含多组数据。第一行为一个正整数T(1 ≤ T ≤ 10),表示有T组测试数据。

对于每组测试数据,仅有一行包含一个整数m(1 ≤ m ≤ 10 ).

Output:

对于每组测试数据,

输出一行包含一个整数,表示A(m, 3) 对(1000000007)取模的结果。

Sample Input:
4
1
2
3
10
Sample Output:
4
16
65536
661944226

Submit