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
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor