Một ông chủ có \(n\) cửa hàng nằm liên tiếp trên một con phố, các cửa hàng được đánh số liên tiếp từ \(1\) đến \(n\) từ đầu phố đến cuối phố. Cửa hàng \(i\) (\(1 \le i \le n\)) có giá trị là \(p_i\).

Ổng chủ có bốn người con và muốn chia \(n\) cửa hàng cho các con của mình theo cách nhau sau.

Ông chọn ba vị trí \(x,y,z\) sao cho \(1 \le x < y < z < n\), gọi \(A = \sum_{i=1}^x p_i = p_1 + ... + p_x\), \(B = \sum_{i=x+1}^y p_i = p_{x+1} + ... + p_y\), \(C = \sum_{i=y+1}^s p_i = p_{y+1} + ... + p_z\) và \(D = \sum_{i=z+1}^n p_i = p_{z+1} + ... + p_n\), khi đó các người con lần lượt nhận các phần tương ứng \(A,B,C,D\). Theo tính toán của ông, giá trị \(S = (AC + BD)^2 + (AD - BC)^2\) càng nhỏ thì các người con càng đồng thuận.

Yêu cầu: Hãy tìm cách chia để giá trị \(S\) càng nhỏ càng tốt.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(p_1, p_2,...,p_n\) (\(p_1 + p_2 + ... + p_n \le 50000\)).

Output

• Gồm một dòng chứa một số nguyên là giá trị \(S\) nhỏ nhất tìm được.

Scoring

• Subtask \(1\) (\(28\%\) số điểm): \(n \le 30\).
• Subtask \(2\) (\(28\%\) số điểm): \(n \le 400\).
• Subtask \(3\) (\(28\%\) số điểm): \(n \le 5000\).
• Subtask \(4\) (\(16\%\) số điểm): \(n \le 50000\).

Example

6
1 1 2 1 1 2

36

Tham gia Đại hội thể htao có \(n\) vận động viên có chiều cao đôi một phân biệt. Đánh số các vận động viên từ \(1\) đến \(n\) vận động viên có chiều cao đôi một phân biệt. Đánh số các vận động viên từ \(1\) đến \(n\), vận động viên thứ \(t\) (\(1 \le t \le n\)) có chiều cao \(h_i\). Theo yêu cầu \(n\) vận động viên sẽ được xếp thành một hàng dọc sao cho không tồn tại bộ ba vận động viên \(i,j,k\) thỏa mãn:

• Vận động viên \(i\) đứng trước vận động viên \(j\), vận động viên \(j\) đứng trước vận động viên \(k\).
• Chiều cao vận động viên \(j\) thấp hơn chiều cao vận động viên \(i\) và chiều cao vận động viên \(i\) thấp hơn chiều cao vận động viên \(k\).

Yêu cầu: Gọi \(s\) là số cách xếp thỏa mãn, tính \(s \% (10^9+7)\), trong đó \(\%\) là phép toán chia lấy dư.

Input

• Dòng đầu chứa số nguyên dương \(n\) (\(n \ge 3\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(h_1,h_2,...,h_n\) (\(h_i \le 10^9\)).

Output

• Gồm một dòng chứa một số nguyên là kết quả bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^3\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^6\).

Example

3
1 2 3

5

Một băng giấy được chia thành \(3 \times n\) ô, mỗi ô được tô bằng màu đen hoặc màu trắng. Cần tìm cách tô để sau khi tô có thể cắt để nhận được một hình chữ nhật màu đen có diện tích bằng \(S\) từ các nhát theo đường chia ô của băng giấy.

Yêu cầu: Cho \(n\) và một số ô đã được tô, hãy đếm số cách tô vào các ô còn lại thỏa mãn yêu cầu trên.

Input

• Dòng đầu hai số nguyên \(n,s\).
• Ba dòng tiếp theo, mỗi dòng chứa một xâu (chỉ gồm ba ký tự W, B, #) độ dài \(n\) mô tả băng.

Output

• Gồm một dòng chứa một số là số cách tô thỏa mãn chia dư cho \(111539786\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 50\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 10^9, s \le 5\) và băng giấy ban đầu chưa tô bất kỳ ô nào (dữ liệu vào khi đó chỉ gồm hai số nguyên \(n,s\)).

Example

2 4
##
##
#W

2

2 4
##
#W
##

0

Quốc gia \(X\) gồm \(N\) hòn đảo được đánh số từ \(1\) đến \(N\). Các hòn đảo được kết nối với nhau bởi \(N - 1\) cây cầu, các cây cầu này đảm bảo từ một hòn đảo có thể đến được bất kì hòn đảo nào khác. Để kích cầu du lịch tại các hòn đảo, chính quyền đang lên kế hoạch xây dựng \(K\) sân bay tại các hòn đảo sao cho hiệu quả nhất. Biết rằng tại hòn đảo \(i\) (\(1 \le i \le n\)) có \(D_i\) người sinh sống. Việc có sân bay gần nơi sinh sống sẽ kích thích người dân đi du lịch, do đó chính quyền mong muốn tìm \(K\) hòn đảo để xây dựng sân bay sao cho tổng khoảng cách từ tất cả người dân sinh sống trong quốc gia đến sân bay gần nhất với người đó càng nhỏ càng tốt. Khoảng cách của một người đến sân bay gần nhất là tổng khoảng cách nhỏ nhất của các cây cầu cần đi qua từ hòn đảo người đó sinh sống đến hòn đảo có sân bay.

Yêu cầu: Hãy tìm các hòn đảo để xây dựng \(K\) sân bay sao cho tổng khoảng cách của tất cả người dân đến sân bay càng nhỏ càng tốt.

Input

• Dòng đầu chứa hai số nguyên dương \(N,K\) (\(1 \le K \le N \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(D_i\) (\(0 \le D_i \le 10^4\)).
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u,v,w\) (\(1 \le u,v \le N, u \neq v, 1 \le w \le 10^4\)) mô tả có cây cầu kết nối hòn đảo \(u\) với hòn đảo \(v\) và có chiều dài là \(w\).

Output

• Ghi ra một dòng gồm \(K\) số là chỉ số của các hòn đảo được chọn để xây sân bay.

Scoring

• Có \(25\) test, mỗi test \(4.0\) điểm. Gọi tổng khoảng cách theo lời giải của thí sinh là \(C\), gọi tổng khoảng cách theo lời giải của giám khảo là \(J\), điểm của thí sinh đạt được cho mỗi test là \(4.0 \times \min\left(1.0,\dfrac{J}{C}\right)\).

Example

5 2
1 2 1 3 2
1 2 2
1 3 1
1 4 3
2 5 1

1 4