All Tracks Algorithms Dynamic Programming Problem

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

enter image description here

\(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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?