Holi and Friendship
Tag(s):

## Advanced, Algorithms, Digit DP, Digit Dp, Dynamic Programming, Medium-Hard

Problem
Editorial
Analytics

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.

SAMPLE INPUT
2
SAMPLE OUTPUT
2

Explanation

The pairs are (0,2) and (1,2).

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

March Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Math > Number Theory
• Algorithms > Graphs
• Algorithms > Dynamic Programming

?