{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThere are $k$ piles of stones in a circle, numbered from $0$ to $k - 1$, where the number of the stones in each pile is $n$ initially. You can do some round operations, where the initial round is numbered as the $1$-st round.\u003cbr\u003e\u003cbr\u003eThe operation of the $i$-th round is to modify the pile of stones numbered $(i - 1) \\bmod k$. In each round, you should remove from this pile some stones (at least one stone), satisfying that the number of stones in this pile before this operation is a multiple of the number of stones in this pile after operation, which means that you ought to remain at least one stone in this pile.\u003cbr\u003e\u003cbr\u003eThe game is ended if there exists at least one pile containing only one stone. Given two positive integers $n$ and $k$, your task is to calculate for each pile the number of the possible operation plans that it is the last operated pile before the game is ended.\u003cbr\u003e\u003cbr\u003eThe integer $n$ may be very large, so the prime-factor decomposition of $n$ will be given, in other words, if $n \u003d \\prod_{i \u003d 1}^{m}{p_i^{e_i}}$, then the integers $m$ and $(p_i, e_i)$ $(1 \\leq i \\leq m)$ will be given, but the integer $n$ will not.\u003cbr\u003e\u003cbr\u003eThe answer may be very large, so you only need to give the value of the answer modulo $985661441$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input contains multiple test cases.\u003cbr\u003e\u003cbr\u003eFor each test case:\u003cbr\u003e\u003cbr\u003eThe first line contains two positive integers $m$ and $k$, satisfying that $1 \\leq m, k \\leq 10$.\u003cbr\u003e\u003cbr\u003eIn next $m$ lines, the $i$-th line contains two positive integers $p_i$ and $e_i$, satisfying that $2 \\leq p_i \\leq 10^9,$ $e_i \\geq 1,$ $\\sum_{i \u003d 1}^{m}{e_i} \\leq 10^5$.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that $p_1, p_2, \\cdots, p_m$ are distinct.\u003cbr\u003e\u003cbr\u003eAbout $200$ test cases in total, where no more than $5$ cases satisfy $\\sum_{i \u003d 1}^{m}{e_i} \\geq 10^4$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output \"\u003cb\u003eCase #$x$: $y_0$ $y_1$ $\\cdots$ $y_{k - 1}$\u003c/b\u003e\" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y_i$ $(0 \\leq i \u0026lt; k)$ denotes the number of the possible operation plans modulo $985661441$ for the pile numbered $i$ of corresponding case."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1\r\n2 2\r\n2 1\r\n3 1\r\n5 1\r\n1 2\r\n2 3\r\n2 2\r\n2 4\r\n5 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 2\r\nCase #2: 3\r\nCase #3: 6 4\r\nCase #4: 1499980 1281085\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}