SAS002 - Apoorv and Math problem


Apoorv is an expert in maths .There are very few questions in maths that Apoorv is unable to answer. Apoorv's teacher is not very fond of Apoorv. So he decided to give Apoorv a  function value to calculate. Apoorv is unable to solve this problem and turns to you for help. Help him to find the answer to the function quickly. Apoorv's teacher will only check the final answer. So Apoorv is free to do calculate the value by any function he likes but the final answer should be same. Also as his teacher don't like him much he gave him a very strict time limit to solve the problem. Help Apoorv in finding the answer quickly.

The function given by Apoorv's teacher is as follows:

function(number) {
              answer = 1
              for ( each i from 1 to number) {
                   if( number modulo i is 0  ) {
                       answer=answer multiplied by i 
                   }
              }
              return answer
          }

Constraints

At max 100 numbers will be given by Apoorv's teacher. The value of number given by Apoorv's teacher will easily fit into 64 bit-integer and will always be positive.

Input

First line will contain t denoting t numbers that are given by Apoorv's teacher.

Next t lines will contain a single integer denoting the number.

Output

For each t numbers output the value of answer in new line. Since the value of answer can be very large Apoorv's teacher is fine with you reporting the answer modulo 109+7.

Example

Input:
2
1
2
Output: 1
2

hide comments
universe_25: 2021-04-08 15:56:06

Maybe this problem is a little naive as an integer factorization problem. :\

kshubham02: 2019-07-02 00:52:38

Damn this is a tiring question :/ :)

smso: 2019-06-24 10:38:07

https://oeis.org/A007955
Similar to:
https://www.spoj.com/problems/NUMDIV/
Beware of (x+y)%mod where numbers are 64-bit

barishnamazov: 2018-06-13 18:19:22

Finally, accepted after fixing tons of overflow bugs :) Nice problem.

nadstratosfer: 2018-03-10 22:27:44

Tanzir Islam, that's most likely down to the probabilistic nature of you-know-what algo you've employed. This problem demands it to be more bullet-proof than usual.

Tanzir Islam: 2018-03-10 09:14:34

@sas1905
Can you check submission id 21298050 and 21297886? They are exactly the same code but the second code got ac but the first code doesn't. By exactly the same, I mean I have copied the second code and resubmitted it. But the resubmission got WA.

Tanzir Islam: 2018-03-10 08:55:17

@orion_pax
There is no test case with n>= (2^63). I checked by asserting the value to be less than (2^63) and it did not get RTE, it got AC.

orion_pax: 2018-03-08 22:07:13

@sas1905 I think test cases are wrong for >=2^63, I simply printed "716550366" for every remaining test case whenever a no. >=2^63 encountered first time in the input and got AC. "716550366" is answer for 2^63 - 1. Correct me if I'm wrong

Last edit: 2018-03-08 23:04:58
sas1905: 2017-12-04 19:07:02

Edit :@ nadstratosfer: Glad you liked the problem :)

Last edit: 2017-12-05 07:17:57
nadstratosfer: 2017-12-04 12:44:50

sas1905, please let me know which case my code fails on. It seems to be passing all the traps I can throw at it. BTW not sure if such cases are in testfiles but for n >= 2^63 judge solution appears to break.

Edit: Thanks Sasmit, got AC with the same code indeed... And again many WA's on retry ;) Great problem, postponed a bunch of errands so I could wrestle with it.

Last edit: 2017-12-04 22:52:30

Added by:sas1905
Date:2017-08-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:College Contests.