406059: GYM102253 D Division Game

There are $$$k$$$ piles of stones in a circle, labeled from $$$0$$$ to $$$(k - 1)$$$, where the number of the stones in each pile is $$$n$$$ initially.

You can do some operations in rounds. The operation of the $$$i$$$-th round is to change the pile labeled $$$((i - 1) \bmod k)$$$, which allows you to remove some (at least one) stones from this pile, such that the old number of stones in this pile is a multiple of the new number. It also implies that you need to keep at least one stone in the pile after this operation.

The game will end if at least one pile contains only one stone. Given the positive integers $$$n$$$ and $$$k$$$, your task is to calculate for each pile, the number of different ways to do operations which can cause the game to end so that this pile is the last changed one.

The integer $$$n$$$ can be gigantic, so $$$n$$$ would be given using its prime factorization, in other words, assuming that $$$n = \prod_{i = 1}^{m}{p_i^{e_i}}$$$ for distinct prime numbers $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_m$$$, $$$m$$$ and $$$(p_i, e_i)$$$ would be given instead of $$$n$$$.

The answer may be fairly large, so you should output the answer modulo $$$985661441$$$ instead.

The input contains multiple (about $$$200$$$) test cases.

For each test case, the first line contains two integers $$$m$$$, $$$k$$$ ($$$1 \leq m, k \leq 10$$$).

The $$$i$$$-th line of the next $$$m$$$ lines contains two integers $$$p_i$$$, $$$e_i$$$ ($$$2 \leq p_i \leq 10^9$$$, $$$e_i \geq 1$$$). It is guaranteed that $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_m$$$ are distinct prime numbers and $$$\sum_{i = 1}^{m}{e_i} \leq 10^5$$$ for each test case.

It is also guaranteed that no more than $$$5$$$ test cases satisfy that $$$\sum_{i = 1}^{m}{e_i} \geq 10^4$$$.

For each test case, output "Case #x: y$$$_{0}$$$ y$$$_{1}$$$ $$$\ldots$$$ y$$$_{k - 1}$$$" in one line (without quotes), where $$$x$$$ indicates the case number starting from $$$1$$$, and $$$y_i$$$ denotes the number of different ways modulo $$$985661441$$$ for the pile labeled $$$i$$$ in the corresponding case.

1 1
2 2
2 1
3 1
5 1
1 2
2 3
2 2
2 4
5 4

Case #1: 2
Case #2: 3
Case #3: 6 4
Case #4: 1499980 1281085