Vertu, the clever businessman, sells the ropes to his customers at the rate of 1 rupee per meter. He can only sell an integer length of a rope to a customer. Also, he has a magic locker which functions this way:

Suppose the locker has 'x' rupees. Now if 'y' rupees more are put into this locker, it multiplies them and total money in the locker now is 'x × y'.

This morning, Vertu starts his bussiness with 'n' meters of rope. He puts 1 rupee in the locker as to have good luck.

Find the maximum money he can earn today considering that he sold all of his rope at the end of the day.

NOTE: Vertu has to put all rupees into the locker as soon as he gets it, and can get rupees from locker only at the end of the day.

Input and Output

The first line contains t, the number of test cases. t lines follow, each containing one positive integer n. For each of these integers, print the required answer modulo (10⁹+7).

Constraints

t < 10⁵

0 < n < 10¹²

Example

Input:
2
4
5

Output:
4
6

---

hide comments

< Previous 1 2 3 4 5 Next >
	[Lakshman]: 2013-12-20 08:21:50 TLE...TLE AC 0.12 Second....
	raunakrocks: 2013-12-20 08:21:50 easy1..AC!!
	Michael Kharitonov: 2013-12-20 08:21:50 @ Ankit Paharia: You need fast i/o and precomputation.
	Ankit Paharia: 2013-12-20 08:21:50 My best time is 0.16 seconds... I want to know how it is AC in 0.00 or 0.01 seconds.. please reply who got AC in 0.00 or 0.01 ...
	daft_wullie: 2013-12-20 08:21:50 Nice problem. Is it possible to get AC with a python solution using an O(logn) algo? --ans(francky)--> Yes it is, check Py3 rank list ;-) But it will be hard. (Py2.7 is possible too). I've let a comment in that way, but author deleted it :-( --edit(Rüdiger)--> Now I got AC using C++ and same algo. I would appreciate to increase time limit for python so that correct algo can pass. Last edit: 2013-04-01 19:44:36