Hợp nhất

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ũ.

Như vậy mỗi bước dãy ngắn đi một phần tử. Lặp lại quá trình này cho đến khi chỉ còn một số duy nhất (nếu $N=1$ thì không cần thực hiện bước nào).

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

Dữ liệu vào

• Dòng 1: số nguyên $N$ $(1\le N\le 5·{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.

Dữ liệu ra

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

Ràng buộc

• $1\le N\le 5·{10}^5$.
• $1\le a_i\le {10}^5$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $1\le N\le 1000$.
• Subtask 2 ($15\%$ số điểm): Mọi phần tử $a_i$ đều bằng nhau.
• Subtask 3 ($40\%$ số điểm): $N\le 100000$.
• Subtask 4 ($15\%$ số điểm): Không có ràng buộc bổ sung.

Ví dụ