背景

注意：本题的时间限制为 6 秒，是默认时间限制的三倍。本题的内存限制为 512 MB，是默认内存限制的两倍。

题目描述

农夫约翰有 $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$，奶牛 $i$ 将独立且随机地选择面朝顺时针或逆时针方向，每个方向有特定的概率。一旦奶牛选择了她的初始方向，她就开始以恒定速度（每分钟一个位置）沿该方向连续移动。当两头奶牛相遇（即它们占据同一位置）时，它们会相互反弹：立即反转它们的方向，并以相同速度继续沿新方向移动。

农夫约翰想知道奶牛 $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}$）。

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

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

提示

对于第一个测试用例，两头奶牛都有 $\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：无额外约束。

翻译由 DeepSeek 完成