Description

Zelda 被给定了两个整数 $l, r$（满足 $l \leq r$），以及两个长度为 $n$ 的序列 $a$ 和 $b$（下标从 $1$ 开始计数）。Zelda 将使用这两个序列进行一个游戏，游戏规则如下：

• 从区间 $[l, r]$ 中 等概率随机 选择一个整数 $x$。
• 对于每一个 $i = 1, 2, \cdots, n$，依次执行以下操作：首先令 $x \gets \min(x, a_i)$，然后令 $x \gets \max(x, b_i)$。

Zelda 想知道最终得到的 $x$ 的期望值。

然而，不幸的是，Zelda 忘记了序列 $a$ 和 $b$ 中的一些整数。因此，她希望你在这些被遗忘的整数也从区间 $[l, r]$ 中 等概率随机选择 的情况下，计算最终 $x$ 的期望值，并将结果对 $10^9 + 7$ 取模。由于 Zelda 将进行多次游戏，因此你需要针对多个不同的 $r$ 值回答查询。

Input Format

输入的第一行包含三个整数 $n, q, l$（$1 \leq n, l \leq 200$，$1 \leq q \leq 5 \times 10^4$），分别表示两个序列的长度、Zelda 游戏的次数，以及随机选择的下界。

第二行包含 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$（$a_i = 0$ 或 $l \leq a_i \leq 200$）。若 $a_i = 0$，则表示该数被 Zelda 忘记。

第三行包含 $n$ 个非负整数 $b_1, b_2, \cdots, b_n$（$b_i = 0$ 或 $l \leq b_i \leq 200$）。若 $b_i = 0$，则表示该数被 Zelda 忘记。

第四行包含 $q$ 个整数 $r_1, r_2, \cdots, r_q$（$l \leq r_i \leq 10^9$），表示每次游戏中对应的 $r$ 值。

Output Format

输出共 $q$ 行，第 $i$ 行输出一个整数，表示第 $i$ 次游戏的答案，对 $10^9 + 7$ 取模。

形式化地，设 $M = 10^9 + 7$。可以证明，答案可以表示为一个既约分数 $\dfrac{p}{q}$，其中 $p, q$ 为整数，且 $q \not\equiv 0 \pmod M$。你应输出满足以下条件的整数：

$$x \equiv p \cdot q^{-1} \pmod M,$$

即输出满足 $0 \leq x < M$ 且 $x \cdot q \equiv p \pmod M$ 的整数。

2 5 1
2 2
0 1
1 2 3 50 538

1
750000007
888888897
857200008
228862927

3 5 2
3 3 0
3 0 0
2 3 4 50 519

2
750000008
962962973
798646858
311741862

Hint

在第一个示例中，序列为 $a = [2, 2]$，$b = [0, 1]$（其中 $b_1 = 0$ 表示被遗忘的值），且有 $q = 5$ 次查询。

在第一次查询中，$l = r = 1$，因此 $x = b_1 = 1$ 始终成立。游戏过程如下：

• 初始时，$x = 1$。
• 当 $i = 1$ 时，首先执行 $x \gets \min(x, a_1) = 1$，然后执行 $x \gets \max(x, b_1) = 1$。
• 当 $i = 2$ 时，首先执行 $x \gets \min(x, a_2) = 1$，然后执行 $x \gets \max(x, b_2) = 1$。

因此第一次查询的答案为 $1$。

在第二次查询中，$l = 1, r = 2$，因此 $x$ 和 $b_1$ 均从区间 $[1, 2]$ 中随机选择。

• 若 $x = 1, b_1 = 1$，则最终 $x = 1$；
• 若 $x = 1, b_1 = 2$，则最终 $x = 2$；
• 若 $x = 2, b_1 = 1$，则最终 $x = 2$；
• 若 $x = 2, b_1 = 2$，则最终 $x = 2$。

每种情况的概率均为 $\dfrac{1}{4}$，因此期望值为

$$\dfrac{1}{4} \times (1 + 2 + 2 + 2) = \dfrac{7}{4}.$$

翻译由 ChatGPT-5 完成