Hide

# Problem DLucky Numbers

Photo by Chris Smith.

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

CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show