[PYTHON] ARC067 C --Factors of Factorial

problem

Find the remainder by dividing the number of positive divisors of $ N! $ By $ 10 ^ 9 + 7 $ when the integer $ N $ is given.

Way of thinking

Let the prime factors of $ N! $ Be {$ p_0, p_1, ..., p_k }. Also, let the number of each prime factor be { i_0, i_1, ..., i_k $}. At this time, $ N! $ Is expressed as follows: N! = p_0^{i_0} \cdot p_1^{i_1} \cdot ... \cdot p_k^{i_k}.

Therefore, the number of divisors of $ N! $ Is (i_0+1) \cdot (i_1+1) \cdot ... \cdot (i_k+1) It becomes.

From the above, it can be seen that the number of divisors can be obtained by finding the number of each prime factor of $ N! $.

Implementation

Here, in order to count the number of each prime factor, $ (Number of prime factors p included in N!) = \ Sigma_ {k = 1} ^ {\ infinty} \ left \ [\ frac {n} {p ^ k} \ right ] = \ left \ [\ frac {n} {p ^ 1} \ right ] + \ left \ [\ frac {n} {p ^ 2} \ right ] + ... $ (Details of this theorem here).

import math
N = math.factorial(int(input()))

res = 1
p = 2  #Factors to check

# p<=sqrt(N)It is enough to investigate the factors that satisfy
while p*p <= N:
    i = 1
    # p^k(k=1~)Count the number of multiples of and add them together
    while(N % p == 0):
        i += 1
        N //= p

    # N!The number of divisors of is i_0*i_1*...*i_k
    res *= i
    p += 1

if(N != 1):
    res *= 2
print(res % (10**9+7))