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.