Cossack Vus and Addition

The renowned Cossack Vus has a lesser-known friend, Vozak Kus, who enjoys adding numbers in columns. However, much to his family's dismay, he often does it incorrectly.

Vozak Kus adds two numbers, $a$ and $b$, each with $n$ digits, using the following method, starting from the last digits:

1. If there is a dot above the current digits, ignore it.

2. Add the corresponding digits of numbers $a$ and $b$ to obtain a number $x$.

3. Write the last digit of $x$ in the corresponding position in the result.

4. If $x>9$, place a dot above the previous digits.

5. Move to the previous digits and repeat from step $1$.

For instance, using Vozak Kus's method, $123+135=258$, and $789+422=101$.

Cossack Vus is curious about how many pairs of numbers $a$ and $b$, each of length $n$, exist for which his friend calculates the sum correctly.

Note that numbers with leading zeros should not be counted. For example, the number $023$ for $n=3$ is invalid. Additionally, the pairs of numbers $(a,b)$ and $(b,a)$ are considered distinct.

Input

The first line contains a single integer $n$ ($1\le n\le 5$).

Output

Output a single number — the answer to the problem.

Examples

Note

Here are some examples of pairs of length $2$: $(21,21)$, $(45,54)$, $(54,45)$, $(10,20)$, etc.