Cho mảng \(A\) gồm \(N\) số nguyên dương.

Yêu cầu: Hãy in ra tổng tất cả các cặp \((A_i \times A_j)\) với mọi cặp \((i,j)\) thỏa mãn \(1\le i < j\le N\) , chia lấy dư cho \(({10}^9+7)\). Hay nói cách khác: tổng tất cả các cặp tích của mảng.

Input

• Dòng đầu tiên nhập số nguyên dương \(N\) \((2\le N\le2\times{10}^5)\).
• Dòng còn lại nhập \(N\) số tiếp theo – là các phần tử của mảng \((1\le A_i\le{10}^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài sau khi chia lấy dư cho \(({10}^9+7)\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(N\le{10}^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 2 3

11

Angry Bird là một chiếc game độc quyền mà ở đó người chơi dùng súng cao su bắn những con chim vào một cảnh một chiều bao gồm một tập hợp các đàn heo nằm ở nhiều điểm khác nhau trên một trục số. Mỗi con chim sau khi bắn sẽ tiếp đất với một lực đủ mạnh để làm nổ các con heo ở gần nơi nó hạ cánh. Mục tiêu là sử dụng một đàn chim để kích nổ tất cả các con heo.

Có \(N\) con heo được đặt ở các tọa độ \(x_1, x_2,...,x_N\) phân biệt trên trục số. Nếu con chim được bắn với lực \(R\) và đáp đất ở vị trị \(x\), vụ nổ diễn ra trong bán kính \(R\), kích nổ tất cả các con heo trong tầm \([x - R, x + R]\).

Tổng cộng có \(K\) con chim đang sẵn sàng để bắn, mỗi con chim đêu bắn với lực \(R\). Hãy xác định giá trị nhỏ nhất của \(R\) để kích nổ được hết tất cả con heo.

Input

• Dòng đầu gồm 2 số nguyên $N, K (0

Một cơ sở sửa chữa ô tô có nhận \(𝑛\) chiếc xe để sửa. Do các nhân viên làm việc quá lười nhác nên đã đến hạn trả cho khách hàng mà vẫn chưa tiến hành sửa được chiếc xe nào. Theo hợp đồng đã ký kết từ trước, nếu bàn giao xe thứ \(𝑖\) quá hạn ngày nào thì sẽ phải trả thêm một khoản tiền phạt là \(𝑎_𝑖\).

Ông chủ cơ sở sửa chữa quyết định sa thải toàn bộ công nhân và thuê nhân công mới. Với lực lượng mới này, ông ta dự định rằng để sửa chiếc xe thứ \(𝑖\) sẽ cần \(𝑏_𝑖\) ngày. Vấn đề đặt ra đối với ông là phải lập lịch sửa tuần tự các chiếc xe sao cho tổng số tiền bị phạt là ít nhất.

Yêu cầu: Hãy lập lịch sửa xe giúp cho ông chủ cơ sở sửa chữa ô tô.

Input

Từ tệp văn bản SCHEDULE.INP gồm:

• Dòng \(1\) chứa số nguyên dương \(n \leq 10^5\).
• Dòng \(2\) chứa \(n\) số nguyên dương \(a_1, a_2, \ldots , a_n, 1 \leq a_i \leq 10^6, \forall i: 1 \leq i \leq n\).
• Dòng \(3\) chứa \(n\) số nguyên dương \(b_1, b_2, \ldots , b_n\), \(1 \leq b_i \leq 10^6\), \(\forall i: 1 \leq i \leq n\).

Output

Ghi ra file văn bản SCHEDULE.OUT gồm một dòng duy nhất ghi số tiền bị phạt tối thiểu.

Example

4
1 3 4 2
3 2 3 1

44

Ngôi làng CLA có rất nhiều ao hồ. Sơ đồ địa lí ngôi làng biểu diễn bằng một bảng ô vuông \(N \times N\). Mỗi ô vuông được biểu diễn bằng một trong hai kí tự:

• . - cho biết vị trí này là ô đất.
• # - biểu thị vị trí này là ô nước.

Một cái ao làng được xác định bằng một vùng các ô vuông #. Hai ô vuông # \(A, B\) thuộc cùng một ao, khi và chỉ khi từ ô \(A\) có thể chèo thuyền qua các ô # sang ô \(B\) và ngược lại, bằng cách di chuyển theo bốn hướng Đông, Tây, Nam, Bắc. Diện tích của ao được xác định bằng số lượng ô vuông thuộc cái ao đó. Chu vi của ao được xác định bằng tổng các ô đất . hoặc đường biên kề cạnh của mỗi ô thuộc cái ao này.

Để chọn một cái ao cho lễ hội năm nay của làng. Trưởng làng đặt yêu cầu cái ao phải có diện tích càng lớn càng tốt, và nếu có nhiều ao cùng diện tích thì chu vi càng nhỏ càng tốt. Do đó, bạn hãy giúp trưởng làng xác định diện tích và chu vi cái ao này nhé.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \le N \le 1000)\)
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) kí tự, mô tả sơ đồ ngôi làng. Các kí tự có thể là . hoặc #.

Output

• In ra diện tích và chu vi của cái ao được chọn thỏa mãn yêu cầu của trưởng làng.

Example

6
##....
....#.
.#..#.
.#####
...###
....##

13 22