The Fate of Ophelia
Ophelia's life would not have been so cruel had she not met Hamlet. The man she loved feigned madness to cast her aside, and then unintentionally took her father's life. Her broken heart drove Ophelia to madness. On that day, while wandering by the riverbank picking flowers, she fell into the water and slowly sank beneath the icy current. She surrendered to fate, making no struggle, ending a sorrowful and anguished life.
The English teacher TayTay was about to meet the same fate. All that time she sat alone in her tower, he was just honing his powers. Late one night, he dug her out of her grave and saved her heart from the fate of Ophelia.
During that dark period, that person (the PE teacher) had always tried to reach her but remained too far away. Refusing to give up, he discovered a secret - a conditional wish tied to the legendary Ophelia. If he fulfilled it, he would be able to reach the one he loved.
"A group of \(N\) scorpions is numbered from 1 to \(N\). When one or more scorpions band together into a group, they generate a power level equal to the product of their indices. A venom of type \(x\) can be produced from a group of scorpions if their power is divisible by \(x\). Across all possible ways of forming groups, determine the number of distinct venom that can be produced from that scorpion swarm."
Please help the PE teacher answer Ophelia's question!
Input
- A single line containing a positive integer \(N \ (1\le N \le 10^5)\).
Output
- A single integer representing the answer to the problem modules \(10^9+7\).
Scoring
- Subtask 1 (30%): \(N \le 10\).
- Subtask 2 (30%): \(N \le 15\).
- Subtask 3 (20%): \(N \le 10^3\).
- Subtask 4 (20%): No additional constraints.
Examples
Example 1
input 3
output
4
Example 2
input 4
output
8
Explanation
The types of venom that can be produced in example 2 are: 1, 2, 3, 4, 6, 8, 12, 24.
Comments