Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Năm 1418, tại núi rừng Chí Linh, lúc ấy nhóm nghĩa quân ít ỏi của Lê Lợi bị giặc Minh vây chặt. Nhiệm vụ của bạn - Vào vai Lê Lai - sẽ đóng giả Lê Lợi để dụ địch.
Tuy nhiên, do có rất nhiều người xung phong, nên chủ tướng Lê Lợi sẽ quyết định tổ chức một cuộc thi - ai ra kết quả nhanh và đúng nhất sẽ được cử đi.
Lê Lợi có N số và ông thực hiện các bước sau đây, sao cho cuối cùng dãy chỉ còn đúng 1 số:

Tính tổng một cặp số nguyên đứng cạnh nhau. Thay thế dãy cũ bằng dãy tổng này.
Tính tích một cặp số nguyên đứng cạnh nhau. Thay thế dãy cũ bằng dãy tổng này.

Các bước thực hiện lần lượt: 1, 2, 1, 2, ... Cho đến khi chỉ còn 1 số. Vì kết quả rất lớn, nên kết quả của các phép tính cộng và nhân được lấy theo modulo 10^9 + 7.
Số cuối cùng là số nào?
Input

Dòng đầu tiên là số nguyên dương N (1 <= N <= 1000)
Dòng tiếp theo chứa dãy số nguyên dương không vượt quá 10^9
Có 50% test có N <= 100

Output

Là số cuối cùng thu được

Example
Input:
6
4 9 3 8 5 7

Output:
161425
 Output: etc.