Description

Given a polynomial $F(x)$, find a polynomial $G(x)$ such that $F(x) * G(x) \equiv 1 ( \mathrm{mod\:} x^n )$. Coefficients are taken modulo $10^9+7$.

Input Format

First input an integer $n$, indicating that $F(x)$ has degree $n-1$. Then input $n$ integers; the $i$-th integer $a_i$ denotes the coefficient of the term of $F(x)$ with degree $i-1$.

Output Format

Output $n$ integers; the $i$-th integer $b_i$ denotes the coefficient of the term of $G(x)$ with degree $i-1$.

5
1 6 3 4 9

1 1000000001 33 999999823 1020

Hint

$1 \leq n \leq 10^5$, $0 \leq a_i \leq 10^9$.

Translated by ChatGPT 5