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.