题目描述
Farmer John 有 $N$ ($1 \leq N \leq 5000$) 头奶牛站在一个圆环形跑道上，跑道被分为 $M$ ($1 \leq M \leq 10^6$) 个等间距的位置，编号为 $0$ 到 $M-1$（顺时针方向）。奶牛 $i$ 最初位于位置 $x_i$，其中 $0 = x_1 < x_2 < \dots < x_N < M$。
对于每头奶牛 $1 \leq i \leq N$，它会独立且随机地选择顺时针或逆时针方向，选择概率由该奶牛特定的参数决定。一旦奶牛选定了初始方向，它便会以每分钟一个位置的恒定速度沿该方向持续移动。当两头奶牛相遇（即它们占据同一位置）时，它们会发生碰撞：立即反转方向，并继续以相同的速度向新方向移动。
Farmer John 想知道奶牛 $1$ 最终会停在哪里。对于每个 $0 \leq i < M$，求出 $K$ ($1 \leq K \leq 10^{18}$) 分钟后奶牛 $1$ 位于位置 $i$ 的概率。
输入格式
第一行包含 $T$ ($1 \leq T \leq 100$)，表示独立测试用例的数量。每个测试用例的格式如下：
每个测试用例的第一行包含 $N$ ($1 \leq N \leq 5000$)，$M$ ($1 \leq M \leq 10^6$) 和 $K$ ($1 \leq K \leq 10^{18}$)。
第二行包含 $N$ 个整数 $p_1, \dots, p_N$ ($0 \leq p_i < 10^9 + 7$)，如果奶牛 $i$ 向顺时针方向移动的概率为 $\frac{a_i}{b_i}$，则满足 $p_i \cdot b_i \equiv a_i \pmod{10^9+7}$。
第三行（最后一行）包含 $N$ 个整数 $x_1, x_2, \dots, x_N$。
保证所有测试用例的 $N^2$ 之和不超过 $5000^2$，且所有测试用例的 $M$ 之和不超过 $10^6$。
输出格式
为每个测试用例输出一行。每行的格式如下：
对于每个 $0 \leq i < M$，设 $\frac{p_i}{q_i}$ 为 $K$ 分钟后奶牛 $1$ 位于位置 $i$ 的概率。输出 $M$ 个空格分隔的整数 $p_iq_i^{-1} \pmod{10^9 + 7}$（其中 $p_iq_i^{-1} \cdot q_i \equiv p_i \pmod{10^9+7}$）。
样例
样例输入 1
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样例输出 1
500000004 500000004
500000004 250000002 250000002
0 0 0 125000001 375000003 0 125000001 375000003 0 0说明 1
对于第一个测试用例，两头奶牛都有 $\frac{1}{2}$ 的概率向任一方向移动。如果两头奶牛选择相同的方向，它们最终会交换位置（因此奶牛 $1$ 最终位于 $1$）。否则，它们会在中间碰撞并弹回各自的初始位置。因此，奶牛 $1$ 最终位于 $0$ 的概率为 $\frac{1}{2}$，位于 $1$ 的概率为 $\frac{1}{2}$。
对于第二个测试用例，所有奶牛同样有 $\frac{1}{2}$ 的概率向任一方向移动。对于每种方向组合，奶牛 $1$ 的最终位置如下：
- 顺, 顺, 顺: $1$
- 顺, 顺, 逆: $1$
- 逆, 逆, 逆: $2$
- 逆, 顺, 逆: $2$
- 顺, 逆, 顺: $0$
- 顺, 逆, 逆: $0$
- 逆, 顺, 顺: $0$
- 逆, 逆, 顺: $0$
子任务
- 输入 2: $K \leq 100, N \leq 10$。
- 输入 3: $N \leq 10$。
- 输入 4-7: $\sum N^3 \leq 500^3$。
- 输入 8-11: $K < \frac{M}{2}$。
- 输入 12-15: 无额外限制。