**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≤N≤5000) cows standing around a circular track divided into M(1≤M≤106) equally spaced positions, numbered 0 to M−1 clockwise. Cow i is initially at position xi , where 0=x1<x2<⋯<xN<M.
For each 1≤i≤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≤i<M, find the probability that cow 1 is at position i after K (1≤K≤1018) minutes.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤100), the number of independent test cases. Each test case is specified as follows:
The first line of each test case contains N(1≤N≤5000), M(1≤M≤106), and K(1≤K≤1018 ).
The second line contains N integers p1,…,pN (0≤pi<109+7) where if ai/bi is the probability cow i goes clockwise, then pi⋅bi≡ai(mod109+7).
The third and final line contains N integers x1,x2,…,xN.
It is guaranteed that the sum of N2 over all test cases is ≤50002 and the sum of M over all testcases is ≤106.
OUTPUT FORMAT (print output to the terminal / stdout):
Output a new line for each test case. The line for each test case should be formatted as follows:
For every 0≤i<M, let pi/qi be the probability cow 1 is in position i at the end of K
minutes. Output M space-separated integers piqi-1 (mod 109+7)
(where piqi-1≡pi(mod 109+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
For the first test case, both cows have a 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 12 chance for cow 1 to end up at 0 and a 12 chance for cow 1 to end up at 1.
For the second test case, all cows again have a 12 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≤100,N≤10.
Input 3: N≤10.
Inputs 4-7: ∑N3≤5003.
Inputs 8-11: K<M/2.
Inputs 12-15: No additional constraints.
Problem credits: Sujay Konda