Karen và Bài kiểm tra

Cho một dãy gồm $n$ số nguyên được viết trên một hàng. Ta thực hiện quá trình sau để rút gọn dãy về một số duy nhất:

• Từ hàng hiện tại, lần lượt cộng rồi trừ xen kẽ mỗi cặp số kề nhau, ghi các kết quả xuống hàng tiếp theo. Phép toán đầu tiên của toàn bộ quá trình là phép cộng.
• Nếu một hàng có $k$ số thì hàng tiếp theo có $k-1$ số.
• Quy tắc nối tiếp giữa các hàng: nếu phép toán cuối cùng của hàng trước là phép cộng thì hàng tiếp theo bắt đầu bằng phép trừ, và ngược lại. Nghĩa là dấu cộng/trừ luân phiên liên tục xuyên suốt tất cả các hàng, không bị đặt lại ở đầu mỗi hàng.

Lặp lại cho đến khi chỉ còn đúng một số. Hãy tìm số cuối cùng đó.

Vì kết quả có thể rất lớn, in ra phần dư không âm khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số lượng phần tử ở hàng đầu tiên.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• Một số nguyên duy nhất: số cuối cùng còn lại, lấy phần dư không âm khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le a_i\le {10}^9$

Ví dụ