406761: GYM102535 R The Only Level 3

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$$$. "

The 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.

3 5

9