Project Euler #92: Square digit chains

_{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

Sample Output