Monk believes in relaxing and playing number games in Holi. Monk's friend defined a Holi function H such that $H(x)$ = sum of digits of number x. Monk is given a question where he will be given a number N and he wants to find the count of number of pairs (x,y) such that the following conditions hold true:

• $0 \le x < y \le N$
• $H(x) < H(y)$
• $H(x)+H(y)$ is prime

$Constraints$

$1\le N \le 10 ^ {50}$

$Input Format$

First line contains N.

$Output Format$

Print the number of pairs modulo 10^9 +7.