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
pranav_167: 2021-08-29 13:25:32

getting time limit exceeded in python language .
where should i post the code?

sankalp_7: 2021-06-24 20:57:20

without break statements ->TLE
with break statements -> accepted

paulpollob: 2021-02-24 23:29:51

wrong answer is showing. can anyone give me some test case please?

Last edit: 2021-02-24 23:30:18
purplecs: 2019-11-17 18:23:44

used Legendre's Formula

anujms: 2019-04-08 20:35:05

Given constraints are incorrect, the code didn't give TLE when I replaced Upper limit from 50000 to 100005

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 :((


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