Description

某一天，qwb去WCfun面试，面试官问了他一个问题：把一个正整数n拆分成若干个正整数的和，请求出这些数乘积的最大值。

qwb比较猥琐，借故上厕所偷偷上网求助，聪明的你能帮助他吗?

Input

第一行为一个正整数T.(T<=100000)

接下来T行，每行一个正整数n(n<=1e9)，意义如题目所述。

Output

每一行输出一个整数，表示乘积的最大值，由于答案可能很大，请将答案对109+7取模后输出。

Sample Input

225

Sample Output

26

HINT

2=2

5=2+3

分析：

很容易看出分成2和3最好，并且6=2+2+2=3+3,222=8，3*3=9，说明尽量分成3.

代码：

#include
    
     #include
     
      #include
      
       #define mod 1000000007using namespace std;int main(){    int T,n,ans,op;    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        ans=1;        op=n/3;        n=n-op*3;        for(int i=1; i<=op; i++)            ans=(ans*3)%mod;        op=n/2;        for(int i=1; i<=op; i++)            ans=(ans*2)%mod;        printf("%d\n",ans);    }    return 0;}