How many numbers

At the faculty of mathematics, Orhan was faced with the following problem: find the number of positive integers from $1$ to $10^n$, which all digits are different.

Since Orkhan also goes to computer science classes at FizMat Lyceum, he easily wrote a program that calculates the answer. And can you do it?

Input

One integer $n(1\le n\le 18)$.

Output

Print the number of required positive integers.

Examples