Equal Digit Products

Time limit1sMemory limit128 MB

Summary

Count N-digit numbers whose digits in odd positions have the same product as the digits in even positions.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Marija likes to play with all sorts of things, numbers among them. This time she asks the following. Given a natural number $N$ , how many natural numbers $X$ with exactly $N$ digits have the product of the digits in even positions equal to the product of the digits in odd positions?

Positions are numbered from left to right. The leading digit, the one with the largest place value, is position 1, so it lies in an odd position. Since $X$ has exactly $N$ digits, the leading digit is not 0.

A product over no digits is defined as 1. So when $N$ is 1 there is no even position and the product of the digits in even positions is 1.

Input

The first and only line contains a natural number $N$ ( $1 \le N \le 14$ ).

Output

Print the number of natural numbers that satisfy the condition.

Examples2

Example 1
Input
```
2
```
Expected output
```
9
```
Example 2
Input
```
3
```
Expected output
```
32
```