You are given sequences ${a_i}_(i = 1)^k$ and ${b_i}_(i = 1)^k$. Consider all sequences ${F_i}_(i = 1)^infinity$ which satisfy the following linear recurrence for all $n > k$:
$$F_n = \sum\limits_{i=1}^k a_i F_{n-i}\text{.}$$
You have to find a sequence ${c_i}_(i = 1)^k$ such that, for all such ${F_i}_(i = 1)^infinity$, the following linear recurrence is satisfied for all $n > b_k$:
$$F_n = \sum\limits_{i=1}^k c_i F_{n-b_i}\text{.}$$
The first line of input contains a single integer $k$ ($1 <= k <= 128$).
The second line of input contains $k$ integers $a_1, \\dots, a_k$ ($1 <= a_i <= 10^9$).
The third line of input contains $k$ integers $b_1, \\dots, b_k$ ($1 <= b_1 < b_2 < \\dots < b_k <= 10^9$).
It is guaranteed that the solution exists and is unique. Moreover, it is guaranteed that sequences $a_i$ and $b_i$ were uniformly randomly chosen among possible ones with some fixed number $k$ for all test cases except the example.
Output $k$ integers $c_1, \\dots, c_k$ on a single line. If $c_k = frac(P, Q)$ such that $P$ and $Q$ are coprime, output $(P dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$.
In the example, we have $F_n = F_(n -1) + F_(n -2)$. We can write $F_n -F_(n -1) = (F_(n -1) + F_(n -2)) -(F_(n -2) + F_(n -3))$. Thus $F_n = 2 F_(n -1) -F_(n -3)$.
## Input
The first line of input contains a single integer $k$ ($1 <= k <= 128$).The second line of input contains $k$ integers $a_1, \\dots, a_k$ ($1 <= a_i <= 10^9$).The third line of input contains $k$ integers $b_1, \\dots, b_k$ ($1 <= b_1 < b_2 < \\dots < b_k <= 10^9$).It is guaranteed that the solution exists and is unique. Moreover, it is guaranteed that sequences $a_i$ and $b_i$ were uniformly randomly chosen among possible ones with some fixed number $k$ for all test cases except the example.
## Output
Output $k$ integers $c_1, \\dots, c_k$ on a single line. If $c_k = frac(P, Q)$ such that $P$ and $Q$ are coprime, output $(P dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$.
[samples]
## Note
In the example, we have $F_n = F_(n -1) + F_(n -2)$. We can write $F_n -F_(n -1) = (F_(n -1) + F_(n -2)) -(F_(n -2) + F_(n -3))$. Thus $F_n = 2 F_(n -1) -F_(n -3)$.
**Definitions**
Let $ k \in \mathbb{Z}^+ $, $ \mathbf{a} = (a_1, \dots, a_k) \in \mathbb{Z}^k $, $ \mathbf{b} = (b_1, \dots, b_k) \in \mathbb{Z}^k $ with $ 1 \le b_1 < b_2 < \dots < b_k $.
Let $ \mathcal{F} $ be the set of all sequences $ F = (F_1, F_2, \dots) $ satisfying the linear recurrence:
$$
F_n = \sum_{i=1}^k a_i F_{n-i}, \quad \forall n > k.
$$
**Constraints**
1. $ 1 \le k \le 128 $
2. $ 1 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, k\} $
3. $ 1 \le b_1 < b_2 < \dots < b_k \le 10^9 $
**Objective**
Find the unique sequence $ \mathbf{c} = (c_1, \dots, c_k) \in \mathbb{Q}^k $ such that for all $ F \in \mathcal{F} $,
$$
F_n = \sum_{i=1}^k c_i F_{n - b_i}, \quad \forall n > b_k.
$$
Output $ c_i \mod (10^9 + 7) $ as $ c_i \equiv P \cdot Q^{-1} \pmod{10^9 + 7} $, where $ c_i = \frac{P}{Q} $ in lowest terms.