LOCKER - Magic of the locker

no tags 

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

hide comments
hemlocktree: 2023-10-07 04:08:25

In simple words, you are given a number n , and break it into parts such that product of all parts is maximum.

sachin_08: 2022-03-23 18:50:07

Hint : Month of the question added !

srinivas_499: 2021-09-30 14:50:10

tle in c++

rachitatrey23: 2021-05-10 14:22:20

can anyone please check my solution n I am getting WA id->27861418

sabbir0152: 2020-07-03 09:12:47

incomplete problem ...

heisunbug: 2020-06-05 11:24:35

Also take care of base case

shuhbo: 2020-05-13 19:41:36

Don't really understand. Python gives me TLE, but c++ gives me accepted.

anurag_mishra: 2020-04-25 03:19:24

modular exponentiation... AC

whoopwhoop: 2020-04-16 10:51:45

@lalitkundu please tell why am i getting a wa my submission id is 25779593

ajay_panchal: 2020-03-27 08:34:03

test case ?


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