Count the Products of Card Numbers

Interview

Time limit1sMemory limit512 MB

Summary

Given n, count the distinct products of n cards, each showing a digit from 1 to 9 with repetition allowed, where n is at most 7.

Level: Easy3 of 10
Topics: Math, Brute force
Solved: No attempts yet

Problem

An infinite supply of cards is given, and each card has an integer from 1 to 9 written on it. Choose $n$ cards from them. You may choose the same card more than once. Let $a$ be the product of the integers on the $n$ chosen cards. Count how many distinct values $a$ can take.

Input

The first line contains the number $n$ of cards to choose.

Output

Print the number of distinct values that $a$ can take on the first line.

Constraints

$1 \le n \le 7$

Examples2

Example 1
Input
```
1
```
Expected output
```
9
```
Example 2
Input
```
2
```
Expected output
```
36
```