{"raw_statement":[{"iden":"statement","content":"You are given sequences ${a_i}_(i = 1)^k$ and ${b_i}_(i = 1)^k$. Consider all sequences ${F_i}_(i = 1)^infinity$ which satisfy the following linear recurrence for all $n > k$:\n\n$$F_n = \\sum\\limits_{i=1}^k a_i F_{n-i}\\text{.}$$\n\nYou have to find a sequence ${c_i}_(i = 1)^k$ such that, for all such ${F_i}_(i = 1)^infinity$, the following linear recurrence is satisfied for all $n > b_k$:\n\n$$F_n = \\sum\\limits_{i=1}^k c_i F_{n-b_i}\\text{.}$$\n\nThe first line of input contains a single integer $k$ ($1 <= k <= 128$).\n\nThe second line of input contains $k$ integers $a_1, \\\\dots, a_k$ ($1 <= a_i <= 10^9$).\n\nThe third line of input contains $k$ integers $b_1, \\\\dots, b_k$ ($1 <= b_1 < b_2 < \\\\dots < b_k <= 10^9$).\n\nIt 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.\n\nOutput $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 dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$.\n\nIn 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 = 2 F_(n -1) -F_(n -3)$.\n\n"},{"iden":"input","content":"The first line of input contains a single integer $k$ ($1 <= k <= 128$).The second line of input contains $k$ integers $a_1, \\\\dots, a_k$ ($1 <= a_i <= 10^9$).The third line of input contains $k$ integers $b_1, \\\\dots, b_k$ ($1 <= b_1 < b_2 < \\\\dots < b_k <= 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."},{"iden":"output","content":"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 dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$."},{"iden":"note","content":"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 = 2 F_(n -1) -F_(n -3)$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ k \\in \\mathbb{Z}^+ $, $ \\mathbf{a} = (a_1, \\dots, a_k) \\in \\mathbb{Z}^k $, $ \\mathbf{b} = (b_1, \\dots, b_k) \\in \\mathbb{Z}^k $ with $ 1 \\le b_1 < b_2 < \\dots < b_k $.  \nLet $ \\mathcal{F} $ be the set of all sequences $ F = (F_1, F_2, \\dots) $ satisfying the linear recurrence:  \n$$\nF_n = \\sum_{i=1}^k a_i F_{n-i}, \\quad \\forall n > k.\n$$\n\n**Constraints**  \n1. $ 1 \\le k \\le 128 $  \n2. $ 1 \\le a_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, k\\} $  \n3. $ 1 \\le b_1 < b_2 < \\dots < b_k \\le 10^9 $  \n\n**Objective**  \nFind the unique sequence $ \\mathbf{c} = (c_1, \\dots, c_k) \\in \\mathbb{Q}^k $ such that for all $ F \\in \\mathcal{F} $,  \n$$\nF_n = \\sum_{i=1}^k c_i F_{n - b_i}, \\quad \\forall n > b_k.\n$$  \nOutput $ c_i \\mod (10^9 + 7) $ as $ c_i \\equiv P \\cdot Q^{-1} \\pmod{10^9 + 7} $, where $ c_i = \\frac{P}{Q} $ in lowest terms.","simple_statement":"Given a linear recurrence $ F_n = \\sum_{i=1}^k a_i F_{n-i} $, and given positions $ b_1 < b_2 < \\dots < b_k $, find coefficients $ c_1, \\dots, c_k $ such that $ F_n = \\sum_{i=1}^k c_i F_{n-b_i} $ for all large enough $ n $. Output the $ c_i $ modulo $ 10^9 + 7 $.","has_page_source":false}