VNG Tech Fresh

Hằng năm, công ty VNG đều tổ chức chương trình VNG Tech Fresh để tuyển chọn và đào tạo các bạn sinh viên tài năng. Năm vừa rồi, có N bạn sinh viên đã xuất sắc vượt qua vòng phỏng vấn để trở thành fresher tại công ty. Các fresher có mã số từ 1 đến N. Fresher có mã số i có năng lực lập trình là C_i.

Hiện tại, người hướng dẫn (mentor) muốn rèn luyện kỹ năng làm việc nhóm cho các bạn fresher. Ban đầu, mỗi người được coi là một nhóm riêng. Ở mỗi bước, mentor sẽ chọn 2 nhóm liền kề và hợp nhất chúng thành 1 nhóm. Khi đó, nhóm mới sẽ có năng lực lập trình bằng bình phương của tổng năng lực lập trình của 2 nhóm được gộp, sau đó chia lấy dư cho $10^9 + 7$.

Mentor hợp nhất theo chiến lược sau. Gọi $F(l, r)$ là năng lực lập trình của nhóm gồm các fresher liên tiếp từ l đến r mà mentor tạo ra:

• Nếu $l = r$ thì $F(l, r) = C_l$ (chưa gộp lần nào, năng lực giữ nguyên, có thể âm).
• Nếu $l < r$ thì mentor chọn một vị trí tách k ($l \leq k < r$), tạo nhóm l..k và nhóm k+1..r theo đúng chiến lược này, rồi gộp hai nhóm đó; mentor chọn k sao cho năng lực sau khi gộp là lớn nhất: $F(l, r) = \max_{l \leq k < r} \left( (F(l, k) + F(k + 1, r))^2 \bmod (10^9 + 7) \right)$.

Lưu ý: mỗi nhóm con luôn là nhóm có năng lực (đã lấy dư) lớn nhất của đoạn của nó, và mọi phép so sánh dùng giá trị đã lấy dư. Vì vậy $F(1, N)$ không nhất thiết là giá trị lớn nhất trong mọi cách hợp nhất tùy ý.

Hãy giúp mentor tính năng lực lập trình $F(1, N)$ của nhóm cuối cùng.

Đầu vào:

• Dòng đầu tiên chứa số nguyên N ($1 \leq N \leq 100$).
• Dòng tiếp theo chứa N số nguyên $C_1, C_2, ... C_N$ ($-10^9 \leq C_i \leq 10^9$).

Đầu ra: In ra một số nguyên duy nhất là $F(1, N)$.

Giải thích: Ban đầu, có 3 nhóm với năng lực lập trình của từng nhóm là:
-3 2 -1
Sau khi hợp nhất nhóm 2 và nhóm 3, ta được
-3 1
Hợp nhất tiếp nhóm 1 và nhóm 2, ta được
4
Cách tách còn lại (gộp nhóm 1 và nhóm 2 trước, $F(1, 2) = 1$) cho $(1 + (-1))^2 = 0$, nên $F(1, 3) = 4$.

Ví dụ 1:

Đầu vào:

3
-3 2 -1

Đầu ra:

4