Basis Change

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

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