Chuyện kể rằng, vào thời điểm năm 1418, một kế hoạch giải cứu chủ nhân tại vùng núi Chi Linh. Lúc nà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ụ lúc này Lê Lại đóng vai Lê Lợi để dụ địch. Tuy nhiên, do có rất nhiều người xung phong, nếu chủ tướng Lê Lợi quyết định sẻ tổ chức một cuoọc thi ai ra kết quả đúng và nhanh nhất sẻ được cử đi.

Lê lợi có N số và ông sẽ thực hiện các bước sau đây, sao cho cuối cùng dãy chỉ còn đúng một số.

1. Tính tổng của mọi cặp số nguyên đứng cạnh nhau và thay thể bởi tổng này;
2. Tính tích của mọi cặp số nguyên đứng cạnh nhau và thay thế bởi tích này;
3. Lặp lại bước 1 …

Các bước được thực hiện lần lượt: 1, 2, 1, 2, 1 .. cho đến khi chỉ còn duy nhất một 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 module ~10^9~+7.

Dữ liệu vào:

Từ tập tin văn bản SMARTEST.INP

• Dòng đầu tiên của dữ liệu vào chứa một số nguyên N – số test.
• N dòng tiếp theo chứa N số nguyên ~a_1, a_2, …. a_N~ (~a_i~ ≤ ~10^9~) cách nhau 1 khoảng trắng.

Dữ liệu ra:

Ghi ra tập tin văn bản SMARTEST.OUT là giá trị tìm được tương ứng với mỗi bộ test.

Subtasks

• Subtask #1 (80 điểm): ~a_i~ <10, N<7
• Subtask #2 (20 điểm): ~a_i~ <~10^9~, N<100

  Ví dụ:

SMARTEST.INP

6 
4 9999 3 8 5 7999

SMARTEST.OUT

161425

Giải thích:

• Dãy biến đổi lần 1: 13, 12, 11, 13,12
• Dãy biến đổi lần 2: 156, 132, 143, 156
• Dãy biến đổi lần 3: 288, 275, 299
• Dãy biến đổi lần 4: 79200, 82225
• Cuối cùng: 161425