题目描述

可恶的肥鲶鱼把伏犬的键盘脚垫拿走了，肥鲶鱼拿走了伏犬n个脚垫，脚垫分成了任意多份（每份的个数都为正整数），肥鲶鱼想利用构造出一个肥鲶鱼数列，使得这个肥鲶鱼数最大。(肥鲶鱼数：每一份的个数相乘得到的数值） 肥鲶鱼没有随身携带计算器，迫切的他想知道他的肥鲶鱼数是多少。希望你可以告诉他答案。

输入

输入包括T+1行。 第一行一个整数T，代表样例个数（0<T<100). 接下来T行，每行一个n，代表肥鲶鱼拿走的键盘脚垫个数。(0<=n<=1000000000)

输出

每组数据有T行输出，每行结果有一个整数，代表肥鲶鱼数，结果可能很大，将结果对1e9+7取模。

样例

2
0
2

0
2