Đây là bài toán số học đơn giản. Bạn có dãy \(N\) số. Thực hiện những bước sau cho đến khi không còn số nào trong \(N\) số đó:

• Tính tổng 2 số liên tiếp. Thay thế 2 số đó bằng tổng của chúng trong dãy mới
• Tính tích của 2 số liên tiếp. Thay thế 2 số đó bằng tích của chúng trong dãy mới

Quá trình thực hiện theo thứ tự: cộng, nhân, cộng, nhân. Vì số có thể rất lớn nên sẽ lấy theo modulo \(10^9+7\)

INPUT

• Dòng đầu tiên ghi số nguyên \(1 ≤ N ≤ 1000.\) Dòng tiếp theo ghi \(N\) số nguyên không âm không vượt quá \(10^9\).

OUTPUT

• In ra 1 số duy nhất là kết quả.

Ví dụ

Input

6
4 9 3 8 5 7

Output

161425

Giải thích

• Cộng: 13, 12, 11, 13, 12.
• Nhân: 156, 132, 143, 156.
• Cộng : 288, 275, 299.
• Nhân: 79200, 82225.
• Cộng: 161425

Ràng buộc

• Trong 50% tổng số test \(N ≤ 100\)