Pseudo-equal Numbers
Problem
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 12 + 42 + 32 is equal to 52 + 12.
Now Mike is interested in counting how many ordered pairs (i, j) are there such that 0 ≤ i, j ≤ 10N and i is pseudo-equal to j.
As the answer can be large print it modulo 109 + 7.
Input format
The only line containing N.
Output format
Print in a single line, the required answer modulo 109 + 7.
Constraints
0 ≤ N ≤ 200
Time Limit: 2
Memory Limit: 128
Source Limit:
Explanation
The required ordered pairs are (0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9), (10, 10), (1, 10), (10, 1). So there are 13 such pairs.
