Divisors of the number N! modulo
Easy
Execution time limit is 1 second
Runtime memory usage limit is 64 megabytes
Given a natural number N, calculate the total number of natural numbers that are divisors of N! (N factorial). Provide the result modulo 1000000009.
Input
The input consists of a single line containing the number N (N ≤ 1000).
Output
Output a single line with the answer to the problem.
Examples
Input #1
Answer #1
Submissions 807
Acceptance rate 26%