CodoHolic is a coding event which is to be organised in Aurora 2K18 under technical events. For the successful conduct of this event, Raman is given an important job of setting coding problems. Raman loves to play with numbers a lot. He recently discovered a special property of numbers and the numbers which followed this property are called Raman-Equal numbers.

Two numbers are known as Raman-Equal numbers if they follow the given property :

• The sum of the squares of the digits of numbers are equal. For e.g , 43 and 50 are Raman-Equal numbers as sum of 4² + 3² is qual to 5² + 0² .

Now, in the question set by Raman he wants you to count the number of ordered pairs (x,y) such that 0<=x,y<=10^N. As the answer to this question can be quite large, he asks you to print it modulo 10⁹+7.

Input :

• The single contains an integer N.

Output :

• A single line containing the answer modulo 10⁹+7.

Constraints :

• 0<=N<=200

See sample example for more details.