406761: GYM102535 R The Only Level 3
Description
You've passed the Only Level TOO.
Your name isn't Mario but you fall down from a pipe.
You find an elephant in a room.
It speaks.
You now know where this is going. The elephant speaks:
" The digital sum of an integer in base $$$b$$$ is the sum of its digits when it is written in base $$$b$$$. The digital root of an integer in base $$$b$$$ is the unique digit obtained by repeatedly computing the digital sum in base $$$b$$$ until only one digit remains.
Let $$$f_b(k)$$$ be the digital root of the integer $$$k$$$ in base $$$b$$$.
We say that the pair $$$(k,b)$$$ is cool if and only if $$$(f_b(0), f_b(k), f_b(2k), \ldots, f_b((b-1)k))$$$ is a permutation of $$$(0, 1, 2, \ldots, b-1)$$$.
Given two integers $$$k'$$$ and $$$b'$$$, find the number of cool pairs $$$(k,b)$$$ such that $$$1 \le k \le k'$$$ and $$$2 \le b \le b'$$$, modulo $$$10^6$$$. "
InputThe input consists of a single line containing two space-separated integers $$$k'$$$ and $$$b'$$$.
Constraints
- $$$1 \le k' \le 5\cdot 10^9$$$
- $$$2 \le b' \le 5\cdot 10^9$$$
Output a single line containing a single integer denoting the answer.
ExampleInput3 5Output
9