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
anil180031050: 2019-02-27 09:53:44

hi guys.i am submitting the code for many testcases it is passing .but it is showing time limit exceeded and can anyone of them give some test cases

knakul853: 2018-10-10 11:34:01

50th : )

s_a_k_s_h_a_m: 2018-06-12 18:27:04

good question! take care of 0! and inverse modulo
used fast factorisation,formula for no of distinct divisors,inverse modulo and little bit of math

ayushgupta1997: 2018-01-02 13:31:27

Used Legendre's Formulation

kspoj: 2017-06-15 19:37:24

same here @pranjalikumar9 :((

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!!!!


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