For a positive integer , let denote the number of positive divisors of .
You are given a positive integer . Compute
The value can be very large, so print modulo .
Input
The input is given from Standard Input in the following format:
Each case is given in the following format:
Output
For each test case, print the remainder of modulo on one line.
Constraints
- .
- .
Subtasks
Samples
Input
4
1
5
10
100
Output
1
10
27
482