Cow Circle

**Note: The time limit for this problem is 6s, thrice the default. The memory limit for this problem is 512MB, twice the default.**

Farmer John has $N$ ( $1 \leq N \leq 5000$ ) cows standing around a circular track divided into $M$ ( $1 \leq M \leq 1 0^{6}$ ) equally spaced positions, numbered $0$ to $M - 1$ clockwise. Cow $i$ is initially at position $x_{i}$ , where $0 = x_{1} < x_{2} < \dots < x_{N} < M$ .

For each $1 \leq i \leq N$ , cow $i$ will independently and randomly choose either to face clockwise or counterclockwise with some probability specific to that cow. Once a cow has chosen her initial direction, she begins moving continuously in that direction at a constant speed of one position per minute. Whenever two cows meet (i.e., they occupy the same space), they bounce off of each other: immediately reversing their directions and continuing to move at the same speed in that direction.

Farmer John is wondering where cow $1$ will end up. For each $0 \leq i < M$ , find the probability that cow $1$ is at position $i$ after $K$ ( $1 \leq K \leq 1 0^{18}$ ) minutes.

For the first test case, both cows have a $\frac{1}{2}$ chance of going in either direction. If both pick the same direction, they will end up swapping positions (so cow $1$ ends up at $1$ ). Otherwise, they will bounce off in the middle and return to their original positions. Therefore, there is a $\frac{1}{2}$ chance for cow $1$ to end up at $0$ and a $\frac{1}{2}$ chance for cow $1$ to end up at $1$ .

For the second test case, all cows again have a $\frac{1}{2}$ chance of going in either direction. For each combination of directions, here is where cow $1$ ends up at.

CW, CW, CW: $1$
CW, CW, CCW: $1$
CCW, CCW, CCW: $2$
CCW, CW, CCW: $2$
CW, CCW, CW: $0$
CW, CCW, CCW: $0$
CCW, CW, CW: $0$
CCW, CCW, CW: $0$

SCORING:

Input 2: $K \leq 100, N \leq 10$ .
Input 3: $N \leq 10$ .
Inputs 4-7: $\sum N^{3} \leq 50 0^{3}$ .
Inputs 8-11: $K < \frac{M}{2}$ .
Inputs 12-15: No additional constraints.

Problem credits: Sujay Konda

Source: USA Computing Olympiad.

Input Format

The first line contains $T$ ( $1 \leq T \leq 100$ ), the number of independent test cases. Each test case is specified as follows:

The first line of each test case contains $N$ ( $1 \leq N \leq 5000$ ), $M$ ( $1 \leq M \leq 1 0^{6}$ ), and $K$ ( $1 \leq K \leq 1 0^{18}$ ).

The second line contains $N$ integers $p_{1}, \dots, p_{N}$ ( $0 \leq p_{i} < 1 0^{9} + 7$ ) where if $\frac{a _{i}}{b _{i}}$ is the probability cow $i$ goes clockwise, then $p_{i} \cdot b_{i} \equiv a_{i} (mod 1 0^{9} + 7)$ .

The third and final line contains $N$ integers $x_{1}, x_{2}, \dots, x_{N}$ .

It is guaranteed that the sum of $N^{2}$ over all test cases is $\leq 500 0^{2}$ and the sum of $M$ over all testcases is $\leq 1 0^{6}$ .

Output Format

Output a new line for each test case. The line for each test case should be formatted as follows:

For every $0 \leq i < M$ , let $\frac{p _{i}}{q _{i}}$ be the probability cow $1$ is in position $i$ at the end of $K$ minutes. Output $M$ space-separated integers $p_{i} q_{i}^{- 1} (mod 1 0^{9} + 7)$ (where $p_{i} q_{i}^{- 1} \cdot q_{i} \equiv p_{i} (mod 1 0^{9} + 7)$ ).

Sample Input

3 2 2 1 500000004 500000004 0 1 3 3 1 500000004 500000004 500000004 0 1 2 5 10 13 500000004 1 500000004 0 500000004 0 3 4 7 9

Sample Output

500000004 500000004 500000004 250000002 250000002 0 0 0 125000001 375000003 0 125000001 375000003 0 0

Submit

Language