Một mảnh đất hình vuông có cạnh là \(100\) mét. Hãy lập trình nhập vào giá trị hai biến \(a,b\) và đưa ra màn hình diện tích mảnh đất hình tam giác được tô (vùng D).

Input

• Gồm một dòng chứa hai số nguyên dương \(a,b\).

Output

• Ghi ra một số nguyên là phần nguyên của diện tích hình tìm được.

Example

10 10

950

Tôi đang nghĩ một phép toán là một trong các phép toán: cộng (\(+\)), trừ (\(-\)) và nhân (\(*\)). Kí hiệu phép toán mà tôi nghĩ là ⊙. Bạn được cho hai số nguyên \(a,b\), bạn hãy đoán xem kết quả \(a\) ⊙ \(b\) bằng bao nhiêu.

Input

• Gồm một dòng chứa hai số nguyên \(a,b\) (\(|a|,|b| \le 2 \times 10^9\)).

Output

• Ghi ra một số mà bạn đoán cho kết quả \(a\) ⊙ \(b\).

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