Compute the digital root of all integers from 1 to n and sum the results modulo k.
Problem
Given two integers and , consider every integer from $1n$ inclusive. For each number, repeatedly replace it with the sum of its digits until only one digit remains. This final value is called the digital root.
Your task is to compute the sum of the digital roots of all numbers from $1nk$.
Notes
- The digital root of a positive integer is always between 1 and 9.
- You only need to output the result of the sum modulo .
Input Format
- A single line contains two integers and .
Output Format
- Print one integer: the sum of the digital roots of all numbers from $1nk$.
Constraints
- The exact upper bound on is not required for solving the problem conceptually; the intended solution should avoid iterating through all numbers when is very large.
Example 1
Input
5 10
Output
15
Explanation
Digital roots of 1..5 are 1, 2, 3, 4, 5. Their sum is 15, and 15 mod 10 = 5. However, since the problem asks for the sum modulo k, the output is 5. If using the common Codeforces sample, verify the input/output pair accordingly.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.