Polynomial Inversion

Given a polynomial \(F(x)\), your task is to compute a polynomial \(G(x)\) such that \(F(x) \cdot G(x) \equiv 1 \pmod{x^n}\). The coefficients are computed modulo \(10^9+7\). More formally, if \(F(x)=F_0+F_1x+\dots+F_{n-1}x^{n-1}\) and \(G(x)=G_0+G_1x+\dots+G_{n-1}x^{n-1}\), then it must hold that

\[ F(x)\cdot G(x) \equiv 1 \pmod{x^n}, \]

i.e., the first \(n\) coefficients (from \(x^0\) to \(x^{n-1}\)) of the product \(F(x) \cdot G(x)\) match those of the constant polynomial \(1\). It is guaranteed that \(F_0\) is invertible modulo \(10^9+7\), so an answer always exists.

inputFormat

The first line contains a single integer \(n\) denoting the number of coefficients and the precision (i.e., we require the inverse modulo \(x^n\)). The second line contains \(n\) space-separated integers \(F_0, F_1, \dots, F_{n-1}\), representing the polynomial \(F(x)=F_0+F_1x+\cdots+F_{n-1}x^{n-1}\). It is guaranteed that \(F_0 \not\equiv 0 \pmod{10^9+7}\).

outputFormat

Output \(n\) space-separated integers which are the coefficients \(G_0, G_1, \dots, G_{n-1}\) of the polynomial \(G(x)\) that is the inverse of \(F(x)\) modulo \(x^n\) under modulo \(10^9+7\).

sample

3
1 2 3

1 1000000005 1