LOCKER - Magic of the locker

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 (109+7).

Constraints

t < 105

0 < n < 1012

Example

Input:
2
4
5

Output:
4
6

Added by:darkshadows
Date:2013-03-28
Time limit:1s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2013-12-20 08:21:50 Shipu Ahamed
@Akhilesh Anandh : N always be greater than zero........ see problem statement.
2013-12-20 08:21:50 ABHISHEK KUMAR
that feeling when u get AC in 1 go....:)
2013-12-20 08:21:50 Akhilesh Anandh
@Lalit Kundu: Please check my code.. I'm getting WA on the 2nd input file. My code is running fine on my computer as well as ideone. Submission id: 9694729.
Also please clarify: for input 0 the answer should be 1 right? (coz he already has 1 rupee in the locker...)
Thanks

Edit: Found my mistake.

Last edit: 2013-08-15 13:33:11
2013-12-20 08:21:50 parikh
can any one provide with test cases...

Last edit: 2013-07-05 05:26:12
2013-12-20 08:21:50 stranger
if you are sure that your code is ok, but you getting WA, then just test your code on http://ideone.com/. the code, that works perfectly on my computer, gives vars overflow on spoj machine

Last edit: 2013-07-04 20:58:51
2013-12-20 08:21:50 vilay
nice problem

Last edit: 2013-06-20 06:02:26
2013-12-20 08:21:50 Rahul Shah
******************...:(
can't allow spoils (author)

Last edit: 2013-06-18 08:46:35
2013-12-20 08:21:50 Amit
modulo costed me 5 WA....finally got AC :)
bdw nice prob !!!
2013-12-20 08:21:50 Pragya Mishra
not dat easy... ;) got the logic at first sight but implementing it and the lack of idea of modular algo costed me many WAs.... phewww.. finallyyy AC!! :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.