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
2019-08-16 16:20:56
I finally got ACCEPTED.
I think that If there is a function in your code that returns nothing your code gets ERRORs on this site.
2019-08-16 16:08:17
Does this problem have an O(N) solution?
My solution is O(NlogN) but it gets TLE.
2019-08-09 15:43:25
AC....
very easy
2018-12-09 21:35:56
take n in long in c++ costed me 2 WA
2018-06-25 11:55:51
learnt map and optimised power code just to pass tle :3
2018-01-03 17:54:58
easy and use up to 1LL<<52:-)
2013-12-20 08:21:50 miodziu
I finally got ACCEPTED, but...

In my opinion, the problem description is not good enough. Why?
There is not described, how/when Vertu can get rupees from locker.

In the example, at the beginnig there is 1 rupee in the locker and 4 more in the hand.
The answer for the example is 4, but when Vertu don't use the locker and just get the 1 rupee, he got 5 rupees (but the correct answer is 4!)

In problem description there is not mentioned, that my scenario is wrong. Moreover, my scenario is better for Vertu.

Please, modify the problem description. Add sentence like this: "Versu has to put all rupees earned into the locker, and can get rupees from locker only at the end"
2013-12-20 08:21:50 hiddenman
gud 1 (y)....learn a lot..... :)
2013-12-20 08:21:50 KESHAV BANSAL
@Lalitkundu pls. tell me y i am getting tle my code id is 9932251
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.