给定序列 $\{a_i\}_{i=1}^k$ 和 $\{b_i\}_{i=1}^k$。考虑所有满足以下线性递推关系（对于所有 $n > k$）的序列 $\{F_i\}_{i=1}^\infty$：

$$F_n = \sum_{i=1}^k a_i F_{n-i}$$

你需要找到一个序列 $\{c_i\}_{i=1}^k$，使得对于所有这样的序列 $\{F_i\}_{i=1}^\infty$，以下线性递推关系对于所有 $n > b_k$ 均成立：

$$F_n = \sum_{i=1}^k c_i F_{n-b_i}$$

输入格式

第一行包含一个整数 $k$ ($1 \le k \le 128$)。 第二行包含 $k$ 个整数 $a_1, \dots, a_k$ ($1 \le a_i \le 10^9$)。 第三行包含 $k$ 个整数 $b_1, \dots, b_k$ ($1 \le b_1 < b_2 < \dots < b_k \le 10^9$)。

保证解存在且唯一。此外，保证除样例外的所有测试用例中，序列 $a_i$ 和 $b_i$ 均是在给定 $k$ 的情况下从可能的值中均匀随机选择的。

输出格式

在一行中输出 $k$ 个整数 $c_1, \dots, c_k$。如果 $c_k = \frac{P}{Q}$ 且 $P$ 与 $Q$ 互质，则输出 $(P \cdot Q^{-1}) \pmod{10^9 + 7}$。保证 $Q \not\equiv 0 \pmod{10^9 + 7}$。

样例

输入 1

2
1 1
1 3

输出 1

2 1000000006

说明

在样例中，我们有 $F_n = F_{n-1} + F_{n-2}$。我们可以写出 $F_n - F_{n-1} = (F_{n-1} + F_{n-2}) - (F_{n-2} + F_{n-3})$。因此 $F_n = 2F_{n-1} - F_{n-3}$。