Supernatural#6082

Supernatural

1 second
128 megabytes
Very easy

We call a natural number supernatural if it does not contain any ones in its decimal representation and the product of its digits is equal to . For given , find how many supernatural numbers exist.

Input

Contains a single integer not exceeding 2 \times 10^9.

Output

Print the total number of supernatural numbers modulo .

Examples

Example 1

Loading
Loading