Cho dãy số nguyên dương ~a_1, a_2, \dots, a_N~.

Một bước biến đổi sẽ tạo ra dãy mới ~b_1, b_2, \dots, b_{N-1}~ với ~b_i = a_i + a_{i+1}~ cho mọi ~1 \le i < N~.

Lặp lại phép biến đổi này cho đến khi chỉ còn đúng một số.

Yêu cầu

Tính giá trị số cuối cùng, lấy theo modulo ~10^9+7~.

Dữ liệu

Dòng ~1~ chứa số nguyên ~N~.

Dòng ~2~ chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~.

Kết quả

In ra một số nguyên là kết quả cần tìm theo modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

5
3 5 4 6 2

Output

73

Giải thích

Ví dụ 1

Ta có: ~[3,5,4,6,2] \to [8,9,10,8] \to [17,19,18] \to [36,37] \to [73]~.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le N \le 5 \cdot 10^5~.

~1 \le a_i \le 10^5~.

Chấm điểm

• Subtask ~1~: ~30\%~ điểm, ~1 \le N \le 1000~.
• Subtask ~2~: ~15\%~ điểm, mọi phần tử ~a_i~ bằng nhau.
• Subtask ~3~: ~40\%~ điểm, ~N \le 10^5~.
• Subtask ~4~: ~15\%~ điểm, không có ràng buộc bổ sung.