DIVFACT - Divisors of factorial


Given a number, find the total number of divisors of the factorial of the number.

Since the answer can be very large, print answer modulo 109+7.

Input

The first line contains T, number of testcases.

T lines follows each containing the number N.

Output

Print T lines of output each containing the answer.

Example

Input:
3
2
3
4

Output:
2
4
8

Constraints

1 <= T <= 500

0 <= N <= 50000


hide comments
marshalsahu: 2017-05-25 20:33:39

don't know why my code is getting wrong on test case 6... anyone here have any idea about it????

rayhan50001: 2017-03-06 18:44:57

nice question i already solved this type of problem like prime factorize of factorial.. it's quite easy when you fiqure out... :D

kira28: 2016-12-09 16:40:25

a typical sieve prob!!!

spartax: 2016-11-26 04:19:53

long caused me 5 WA's

sandeep_4141: 2016-10-30 08:09:44

used sieve and a little bit math.AC in one go!!!!

Rafail Loizou: 2016-06-30 19:55:35

0! = 1 (I didn't knew that till now... COST ME A LOT OF WAs)

vineetpratik: 2016-06-25 12:43:26

take care of mod 1000000007 cost me WA , use sieve and power of prime in a given factorial

wesolyfoton: 2016-06-20 01:20:35

Try FCTRL first.

pranjalikumar9: 2016-05-28 21:09:24

something is wrong..my code is giving correct answers for all testcases in spoj toolkit and others i could think of..Can THE AUTHOR tell me what is wrong with my code?

sahil_420420: 2016-05-24 20:23:50

Hey author, please check my code,its giving right answers to almost each one, and stated correct by a frnd having ac in this , please tell me where i m wrong.......


Added by:ivar.raknahs
Date:2015-01-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own