{"problem":{"name":"R. The Only Level 3","description":{"content":"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 *dig","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10253R"},"statements":[{"statement_type":"Markdown","content":"You've passed the Only Level TOO.\n\nYour name isn't Mario but you fall down from a pipe.\n\nYou find an elephant in a room.\n\nIt speaks.\n\nYou now know where this is going. The elephant speaks:\n\n\" 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. \n\nLet $f_b (k)$ be the digital root of the integer $k$ in base $b$.\n\nWe say that the pair $(k, b)$ is *cool* if and only if $(f_b (0), f_b (k), f_b (2 k), \\\\dots, f_b ((b -1) k))$ is a permutation of $(0, 1, 2, \\\\dots, b -1)$. \n\nGiven two integers $k '$ and $b '$, find the number of cool pairs $(k, b)$ such that $1 <= k <= k '$ and $2 <= b <= b '$, modulo $10^6$. \"\n\nThe input consists of a single line containing two space-separated integers $k '$ and $b '$. \n\n*Constraints*\n\nOutput a single line containing a single integer denoting the answer. \n\n## Input\n\nThe input consists of a single line containing two space-separated integers $k '$ and $b '$. *Constraints*  $1 <= k ' <= 5 dot.op 10^9$  $2 <= b ' <= 5 dot.op 10^9$ \n\n## Output\n\nOutput a single line containing a single integer denoting the answer. \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ f_b(k) $ denote the digital root of $ k $ in base $ b $, defined as the repeated sum of digits in base $ b $ until a single digit is obtained.  \n\n**Constraints**  \nGiven integers $ k' \\in \\mathbb{Z}^+ $, $ b' \\in \\mathbb{Z}^+ $ with $ 1 \\leq k' \\leq 10^6 $, $ 2 \\leq b' \\leq 10^6 $.  \n\n**Objective**  \nCount the number of pairs $ (k, b) $ such that:  \n- $ 1 \\leq k \\leq k' $,  \n- $ 2 \\leq b \\leq b' $,  \n- The sequence $ \\left( f_b(0), f_b(k), f_b(2k), \\dots, f_b((b-1)k) \\right) $ is a permutation of $ \\{0, 1, 2, \\dots, b-1\\} $.  \n\nOutput the count modulo $ 10^6 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10253R","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}