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 Haijun Deng
O(log(n)) got TLE. Any suggestion?
2013-12-20 08:21:50 Alien
finally got AC , its a easy one if you use modular algo,
2013-12-20 08:21:50 Alien
@Akash your code will give wrong ans *****
no spoils (author)

Last edit: 2013-06-18 08:47:12
2013-12-20 08:21:50 Akash
Why am i always getting TLE even though my code(python 3.3.2) runs very fast even for n>>10^12
plzz check it..
<snip>
Edit: ****** but this TLE is giving me a headache..looks like python is very slow..:(
Same code AC in C..:P
no spoils (author)

Last edit: 2021-10-01 01:26:33
2013-12-20 08:21:50 chicku
@Lalit Kundu please tell me why i am getting wrong answer my code id=9359514...also whats the ans for 10^12

Last edit: 2013-05-27 16:36:31
2013-12-20 08:21:50 chk
learnt 2 new things,nice problem :)
2013-12-20 08:21:50 Atul Kumar Verma
Learned something new in this problem Finally AC!!!
2013-12-20 08:21:50 Ouditchya Sinha
Nice Problem. :)
2013-12-20 08:21:50 [Lakshman]
@pushpendra chauhan As per the problem initilly he starts with one rupee in locker
now he have 4 meter of rope in order to maximize the profit he will sell the rope one of 2 and other one of 2 meter and he will get 1*2*2 rupee in locker
for 5 meter rope he will sell it one of 3 meter and other of 2 meter and he will get 1*2*3 rupee..in locker

Last edit: 2013-04-16 11:38:31
2013-12-20 08:21:50 Goldie
Please explain the TCs .. I am not able to understand the question. How for input 4 max profit is 4 and for 5 max profit is 6.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.