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

Ví dụ:

Dữ liệu

• Dòng 1: số nguyên N (N<10^5) – số phần tử ban đầu của dãy.
• Dòng 2: N số nguyên a1, a2, …aN – các phần tử của dãy ban đầu.

Kết quả

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