Problem D
Lucky Numbers
Mr. Lucky has a store that sells numbers. These numbers have an interesting property: each number formed by its first $k$ digits is evenly divisible by $k$, for $k$ from $1$ to $n$, where $n$ is the number of digits in the number. The numbers do not have leading zeroes.
Mr. Unlucky wants to open a competing store. Price for lucky numbers is driven by demand and supply, and given by the formula
\[ \mbox{price} = \frac{\mbox{demand}}{\mbox{supply}} \]while demand for numbers with $n$ digits is given by the formula
\[ \mbox{demand} = \mbox{citySize} \cdot \mbox{dayOfMonth} - n^ e \]where $e$ is the base of the natural logarithm. Supply for lucky numbers with $n$ digits is simply the number of lucky numbers with $n$ digits. Help Mr. Unlucky calculate the supply for $n$ digit lucky numbers.
Input
The input is a single integer $n$.
Output
Output the supply for $n$ digit lucky numbers.
Limits
-
$2 \leq n \leq 1\, 000$
| Sample Input 1 | Sample Output 1 |
|---|---|
2 |
45 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 |
150 |
