题目描述

给定一条线段，将该线段分割成整数长度互不相同的若干小段（可只有一段），使得这些小段长度的乘积最大。求这个最大的乘积。

输入格式

第一行给定整数 $T$，代表测试组数.

接下来 $T$ 行。每行包含一个整数 $x$，代表线段的长度. $1≤T≤10^6,1≤x≤10^9$

输出格式

最大乘积 $S$ 模 $10^9+7$

样例

1
4

4

样例解释

最佳策略是4=4（不分段） 它比诸如1+3（结果为1*3=3）等策略更优