시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB35161544.118%

문제

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}\).