- Time limit: 1.00 s
- Memory limit: 128 MB
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.