Given $n$ integers $a_1, a_2, \ldots a_n$, calculate the product $a_1 \cdot a_2 \cdot \ldots \cdot a_k$ for every $k = 1, 2, \ldots, n$. The results will be very large, so calculate them modulo $10^9+7$ (1000000007).

Input

The first line contains a single integer $n$. The second line contains $n$ integers $a_1, a_2, \ldots a_n$.

Output

Output $n$ integers separated by spaces representing the products modulo $10^9+7$.

Constraints

• $1 \le n \le 10^5$
• $1 \le a_i \le 10^9$

Examples

Input:

5
5 2 3 2 6

Output:

5 10 30 60 360

Input:

4 
100000 100000 1000000000 2

Output:

100000 999999937 490 980

Note

For an explanation of the modulo operation, see this Wikipedia article.