Một khu vực nghiên cứu có dạng một đa giác đều gồm ~n~ đỉnh. Tại mỗi đỉnh đặt một trạm quan sát; các trạm được đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ. Số ~n~ luôn là một số lẻ.

Trạm thứ ~i~ có ~a_i~ thiết bị quan sát phân biệt. Một trạm có thể không có thiết bị.

Cần chọn đúng ba thiết bị thuộc ba trạm đôi một khác nhau. Ba trạm được chọn tạo thành một tam giác.

Một cách chọn được xem là hợp lệ nếu tâm của đa giác nằm hoàn toàn bên trong tam giác. Trường hợp tâm nằm trên một cạnh hoặc trùng với một đỉnh của tam giác không được tính.

Hai cách chọn được xem là khác nhau nếu có ít nhất một thiết bị được chọn khác nhau.

Hãy tính số cách chọn hợp lệ. Vì kết quả có thể rất lớn, hãy in kết quả theo modulo ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên lẻ ~n~, là số trạm quan sát;

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~, trong đó ~a_i~ là số thiết bị ở trạm thứ ~i~.

Output

In ra một số nguyên duy nhất là số cách chọn hợp lệ, lấy theo modulo ~10^9 + 7~.

Scoring

• ~3 \le n \le 2 \cdot 10^5~;

• ~n~ là số lẻ;

• ~0 \le a_i \le 10^9~.

Sample Input 1

3
2 3 4

Sample Output 1

24

Sample Input 2

5
1 1 1 1 1

Sample Output 2

5

Sample Input 3

5
2 1 1 1 1

Sample Output 3

8

Notes

Test 1: Ba trạm tạo thành chính tam giác đều ban đầu và tâm tam giác này chứa tâm đa giác. Có ~2 \cdot 3 \cdot 4 = 24~ cách chọn một thiết bị từ mỗi trạm.

Test 2: Mỗi trạm chỉ có một thiết bị. Có đúng ~5~ bộ ba trạm tạo thành tam giác chứa tâm ngũ giác.

Test 3: Trong ~5~ bộ ba trạm tạo thành tam giác chứa tâm, có ~3~ bộ ba chứa trạm thứ nhất và ~2~ bộ ba không chứa trạm thứ nhất. Vì vậy số cách chọn là ~3 \cdot 2 + 2 = 8~.