Bessie đang cùng bạn bè chơi một tựa game online nổi tiếng. Mục tiêu của game là điều khiển một tế bào đi hấp thụ những tế bào khác cho đến khi chỉ còn một tế bào duy nhất thống trị bản đồ.

Có tất cả \(N\) (\(2 \leq N \leq 5000\)) tế bào, được đánh dấu từ \(1\) đến \(N\) xếp thành một hàng từ trái sang phải, với kích thước ban đầu của mỗi tế bào là \(s_1, s_2, \ldots, s_N\) (\(1 \leq s_i \leq 10^5\)). Những tế bào ở cạnh nhau sẽ được bắt cặp ngẫu nhiên và phải chiến đấu với nhau. Tế bào có kích thước lớn hơn sẽ chiến thắng và hấp thụ tế bào còn lại và tăng kích thước của bản thân lên một giá trị bằng với kích thước của tế bào kia. Trong trường hợp hòa nhau, người có số thứ tự lớn hơn sẽ được tính là chiến thắng.

Với mỗi người chơi, hãy tìm ra tỉ lệ người chơi đó trở thành tế bào cuối cùng và chiến thắng trò chơi. Tỉ lệ chiến thắng của người đó có thể biểu thị dưới dạng \(\frac{a_i}{b_i}\), trong đó \(b \not\equiv 0 (\text{mod } 10^9 +7)\). Hãy in ra \(a_ib_i^{-1} (\text{mod } 10^9 +7)\).

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng tiếp theo chứa \(N\) giá trị \(s_1, s_2, \ldots, s_N\).

Output

• Gồm \(N\) dòng, dòng thứ \(i\) là tỉ lệ chiến thắng của tế bào thứ \(i\). In ra kết quả theo modulo \(10^9 +7\).

Scoring

• Subtask 1: \(N \leq 8\)
• Subtask 2: \(N \leq 100\)
• Subtask 3: \(N \leq 500\)
• Subtask 4: Không có ràng buộc gì thêm.

Example

3
1 1 1

0
500000004
500000004

4
3 1 1 1

666666672
0
166666668
166666668