Q Từng hỏi C rằng cậu có biết loài hoa mà tớ thích nhất không?
C: Hmmm hoa hướng dương chăng, vì nó rực rỡ như cậu vậy
Q: Hay vậy cậu đoán đúng rồi nhưng mà nó phải thỏa mãn một số điều kiện sau cơ:

Ở ngọn đồi nơi mà C và Q sinh sống có ~n~ bông hoa hướng dương và các hoa có số cánh hoa là ~a_i~ với ~1 \le i \le n~. Vì rất thích người bạn của mình nên C quyết định thu thập ba bông hoa ~i, j, k~ để tặng cho cậu ấy, sao cho ba bông hoa ấy thỏa mãn các điều kiện sau:

• ~a_i < a_j < a_k < a_i + a_j.~

• ~19a_i+19a_j+6a_k~ chia hết cho ~7~ hoặc ~6~.

Biết rằng độ rực rỡ của bó hoa được tính bằng: ~a_i+a_j-a_k.~

Hãy tính TÍCH độ rực rỡ của các bó hoa mà C có thể thu thập được. Nếu không thu thập được bó hoa nào hãy in ra ~0~. biết rằng điều này sẽ khiến C buồn :<

Input:

• Dòng đầu tiên gồm một số nguyên ~N~ với ~1 \le N \le 10^5~.

• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ với ~1 \le a_i \le 3 \cdot 10^3~.

Output:

TÍCH độ rực rỡ các bộ ba ~(i,j,k)~ thỏa mãn điều kiện và MOD cho ~10^9+7~.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

1

Sample Input 2

5
1 3 7 6 2

Sample Output 2

0

Giải thích

Trong VD1, các bộ thỏa mãn sẽ là ~(2,3,4),(2,4,5)~ và đều có cùng độ rực rỡ là ~1~, vì thế đáp số là ~1^2 = 1.~ Còn trong VD2, C đã không có bó hoa nào và bạn ấy buồn lắm.

Bạn biết không, ở ngọn đồi đó làm gì mà có hoa hướng dương...