시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 8 8 57.143%

문제

You are given sequences $\{a_i\}^{k}_{i=1}$ and $\{b_i\}^{k}_{i=1}$. Consider all sequences $\{F_i\}^{\infty}_{i=1}$ which satisfy the following linear recurrence for all $n > k$:

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

You have to find a sequence $\{c_i\}^{k}_{i=1}$ such that, for all such $\{F_i\}^{\infty}_{i=1}$, the following linear recurrence is satisfied for all $n > b_k$:

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

입력

The first line of input contains a single integer $k$ ($1 \le k \le 128$).

The second line of input contains $k$ integers $a_1, \dots , a_k$ ($1 \le a_i ≤ 10^9$).

The third line of input contains $k$ integers $b_1, \dots , b_k$ ($1 \le b_1 < b_2 < \cdots < b_k \le 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 \cdot Q^{−1}$) mod ($10^9 + 7$). It is guaranteed that $Q \not\equiv 0$ (mod $10^9 + 7$).

예제 입력 1

2
1 1
1 3


예제 출력 1

2 1000000006


힌트

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 = 2F_{n−1} − F_{n−3}$.