Cho một dãy số nguyên dương gồm ~N~ phần tử. Tại mỗi bước, tạo ra một dãy mới bằng cách cộng từng cặp phần tử liên tiếp trong dãy hiện tại:

• Phần tử thứ nhất của dãy mới là tổng của phần tử thứ nhất và thứ hai của dãy cũ,

• Phần tử thứ hai là tổng của phần tử thứ hai và thứ ba của dãy cũ,

• ~\dots~,

• Phần tử cuối cùng là tổng của hai phần tử cuối cùng của dãy cũ.

Lặp lại quá trình này cho đến khi chỉ còn một số duy nhất.

Hãy tính giá trị của số cuối cùng này, lấy theo modulo ~(10^9 + 7)~.

Input

• Dòng 1: số nguyên ~N~ ~(1 \le N \le 5 \cdot 10^5)~ - số phần tử ban đầu của dãy.

• Dòng 2: ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^5)~ - các phần tử của dãy ban đầu.

Output

• Dòng 1: số nguyên kết quả, lấy modulo ~(10^9 + 7)~.

Scoring

Sample Input 1

5
3 5 4 6 2

Sample Output 1

73

Notes

~[3,5,4,6,2] \rightarrow [8,9,10,8] \rightarrow [17,19,18] \rightarrow [36,37] \rightarrow [73]~.