This problem is a programming version of Problem 92 from projecteuler.net
A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.
For example,
Therefore any chain that arrives at or will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at or .
How many starting numbers below will arrive at ? As the result can be large, print modulo
Input Format
First and only line contains .
Constraints
Output Format
Print the required answer.
Sample Input
1
Sample Output
7