405822: GYM102129 D Basis Change

You are given sequences $$$\{a_i\}_{i=1}^k$$$ and $$$\{b_i\}_{i=1}^k$$$. Consider all sequences $$$\{F_i\}_{i=1}^\infty$$$ 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}^\infty$$$, 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 \leq k \leq 128$$$).

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

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

2
1 1
1 3

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}$$$.