Mike is very much fond of numbers. Two numbers are defined as pseudo-equal if sum of squares of their digits is equal. For example, 143 is pseudo-equal to 51 as 1² + 4² + 3² is equal to 5² + 1².

Now Mike is interested in counting how many ordered pairs (i, j) are there such that 0 ≤ i, j ≤ 10^N and i is pseudo-equal to j.

As the answer can be large print it modulo 10⁹ + 7.

Input format

The only line containing N.

Output format

Print in a single line, the required answer modulo 10⁹ + 7.

Constraints

0 ≤ N ≤ 200