G. Digit analysis
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Daniyar has finally graduated from school! Right now he is studying Digit Analysis. In particular, he is learning about various sequences. Professor challenged students to come up with original fast-growing sequences.

Daniyar came up with the sequence $$$(d_n)_{n \in \mathbb{N}}$$$. To calculate the $$$n$$$-th term of the sequence, Daniyar uses the following process. First, he lists all natural numbers, that have the sum of digits equal to $$$n$$$. Then, he replaces each of those numbers with the products of their digits. After that, Daniyar erases duplicates in his list, so that each number occurs exactly once. Finally, he writes down how many numbers are left as $$$d_n$$$.

As you can see, this is a long process and Daniyar forgot how to code years ago. Help him to write a program that calculates $$$d_n$$$ for a given $$$n$$$. Since $$$d_n$$$ might be very large, count it modulo $$$10^9 + 7$$$.

Input

The only line of the input contains a single positive integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Output

Print a single integer $$$d_n$$$. Since this number might be very large, print it modulo $$$10^9 + 7$$$.

Examples
Input
3
Output
4
Input
7
Output
12
Note

Number $$$111$$$ has a sum of digits equal to $$$3$$$. Daniyar replaces the number by its digit product and obtains $$$1$$$.

Number $$$21$$$ has a sum of digits equal to $$$3$$$. Daniyar replaces the number by its digit product and obtains $$$2$$$.

Number $$$3$$$ also has a sum of digits equal to $$$3$$$. Daniyar replaces the number by its digit product and obtains $$$3$$$.

Number $$$201$$$ also has a sum of digits equal to $$$3$$$. Daniyar replaces the number by its digit product and obtains $$$0$$$.

It can be shown that there are no more distinct values we can get, thus the answer is $$$4$$$.