All Tracks Algorithms Dynamic Programming Problem

Holi and Friendship
/

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
通知
View All Notifications

?