给定整数 $l, r$ ($l \le r$)，Zelda 有两个长度为 $n$ 的序列 $a$ 和 $b$，下标从 $1$ 到 $n$。

Zelda 将使用这两个序列玩一个游戏，游戏过程如下：

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

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

不幸的是，Zelda 忘记了序列 $a$ 和 $b$ 中的一些整数，因此她希望你计算当所有被遗忘的整数也从区间 $[l, r]$ 中等概率随机选择时，最终 $x$ 的期望值模 $10^9 + 7$ 的结果。由于 Zelda 会玩多次游戏，你需要回答多个不同 $r$ 值的询问。

输入格式

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

下一行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ ($a_i = 0$ 或 $l \le a_i \le 200$)。$a_i = 0$ 表示该整数被 Zelda 忘记了。

下一行包含 $n$ 个非负整数 $b_1, b_2, \dots, b_n$ ($b_i = 0$ 或 $l \le b_i \le 200$)。$b_i = 0$ 表示该整数被 Zelda 忘记了。

下一行包含 $q$ 个整数 $r_1, r_2, \dots, r_q$ ($l \le r_i \le 10^9$)，表示每次 Zelda 玩游戏时 $r$ 的值。

输出格式

输出包含 $q$ 行，其中第 $i$ 行包含一个整数，表示第 $i$ 次游戏的答案模 $10^9 + 7$ 的结果。

形式化地，设 $M = 10^9 + 7$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod M$。输出等于 $p \cdot q^{-1} \pmod M$ 的整数。换句话说，输出一个满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod M$ 的整数 $x$。

样例

输入样例 1

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

输出样例 1

1
750000007
888888897
857200008
228862927

输入样例 2

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

输出样例 2

2
750000008
962962973
798646858
311741862

说明

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

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

• 初始时，$x = 1$。
• 对于 $i = 1$ 执行操作：首先 $x \leftarrow \min(x, a_1) = 1$，然后 $x \leftarrow \max(x, b_1) = 1$。
• 对于 $i = 2$ 执行操作：首先 $x \leftarrow \min(x, a_2) = 1$，然后 $x \leftarrow \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$。

每种情况的概率均为 $\frac{1}{4}$，因此第二次询问的答案为 $\frac{1}{4} \times (1 + 2 + 2 + 2) = \frac{7}{4}$。