Khu Tèo sống đang tổ chức một sự kiện phát quà cho những bạn hiếu học, nhưng việc kì lạ ở đây chính là cách họ phát quà. Ban tổ chức sẽ chia ra ~Q~ đợt phát quà, mỗi đợt gồm ~N~ bạn được đánh số từ 1 đến ~N~, bạn đầu tiên sẽ được nhận ~A~ quà, bạn thứ ~2~ nhận nhiều hơn bạn đầu tiên ~B~ quà, bạn thứ ~3~ nhận nhiều hơn bạn thứ hai ~B~ quà, ~\dots~, cứ như vậy cho đến cuối.

Tèo thắc mắc cứ mỗi đợt phát thưởng, bạn cuối cùng sẽ nhận được bao nhiêu quà? Là một người bạn của Tèo, bạn hãy giúp Tèo trả lời nhé!

Dữ liệu vào

• Dòng đầu tiên gồm một số nguyên dương ~Q~ ~(1 \leq Q \leq 5 \times 10^{5})~ là số đợt phát thưởng.
• Dòng thứ ~2~ gồm ~Q~ số nguyên dương ~N_{1}, N_{2}, \dots, N_{Q}~ là số bạn nhận quà ở đợt thứ ~i~ ~(1 \leq N_{i} \leq 10^{12})~.
• Dòng thứ ~3~ gồm ~Q~ số nguyên dương ~A_{1}, A_{2}, \dots, A_{Q}~ ~(1 \leq A_{i} \leq 10^{12})~.
• Dòng thứ ~4~ gồm ~Q~ số nguyên dương ~B_{1}, B_{2}, \dots, B_{Q}~ ~(1 \leq B_{i} \leq 10^{12})~.

Kết quả ra

• In trên một dòng gồm ~Q~ số nguyên dương là kết quả bài toán của đợt phát thưởng tương ứng được chia lấy dư cho 1000000007.

Ràng buộc

• Subtask ~1~ ~(30 \%)~ : ~1 \leq Q \leq 5000, 1 \leq N_{i} \leq 1000~.
• Subtask ~2~ ~(70 \%)~ : Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

3
1 2 3
2 3 4
3 4 5

Kết quả ra

2 7 14

Giải thích

• Ở đợt ~1~: Bạn thứ ~1~ sẽ nhận được ~2~ phần quà.
• Ở đợt ~2~: Số phần quà của từng bạn lần lượt là : ~3, 7~.
• Ở đợt ~3~: Số phần quà của từng bạn lần lượt là : ~4, 9, 14~.