{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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$ "},{"iden":"output","content":"Output a single line containing a single integer denoting the answer. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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 $.","simple_statement":"Given two integers k' and b', count how many pairs (k, b) with 1 ≤ k ≤ k' and 2 ≤ b ≤ b' are \"cool\", where a pair is cool if the digital roots of 0, k, 2k, ..., (b-1)k in base b form a permutation of 0, 1, 2, ..., b-1. Answer modulo 10^6.","has_page_source":false}