기저 변환

수열 \(\{a_i\}^{k}\{i=1}\)과 \(\{b_i\}^{k}\{i=1}\)이 주어진다. 모든 \(n > k\)에 대해 다음 선형 점화식을 만족하는 모든 수열 \(\{F_i\}^{\infty}\_{i=1}\)을 생각하자.

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

그러한 모든 \(\{F_i\}^{\infty}\{i=1}\)에 대해, 모든 \(n > b_k\)에서 다음 선형 점화식이 성립하게 하는 수열 \(\{c_i\}^{k}\{i=1}\)을 구해야 한다.

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

첫째 줄에 정수 \(k\)가 주어진다. (\(1 \le k \le 128\))

둘째 줄에 \(k\)개의 정수 \(a_1, \dots , a_k\)가 주어진다. (\(1 \le a_i \u2264 10^9\))

셋째 줄에 \(k\)개의 정수 \(b_1, \dots , b_k\)가 주어진다. (\(1 \le b_1 < b_2 < \cdots < 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}\)) mod (\(10^9 + 7\))을 출력한다. \(Q \not\equiv 0\) (mod \(10^9 + 7\))임이 보장된다.

예제에서 \(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}\)이다.