Cho một mảng gồm ~N~ phần tử ~a_1, a_2, \ldots, a_N~. Một bộ ~3~ số ~a_i, a_j, a_k~ được gọi là đẹp nếu ~a_i < a_j < a_k < a_i + a_j~ và ~3 \times a_i + 3 \times a_j + 5 \times a_k~ là một số chia hết cho ~3, 5~ hoặc ~8~. Hai bộ ~3~ được gọi là khác nhau nếu tồn tại một vị trí xuất hiện trong bộ này nhưng không xuất hiện trong bộ còn lại.

Ta định nghĩa độ đẹp của bộ ~3~ số đẹp ~a_i, a_j, a_k~ là biểu thức: ~a_i + a_j - a_k~. Hãy tính tích độ đẹp của tất cả các bộ ba số đẹp, nếu không tồn tại bất kì một bộ ba nào đẹp in ra ~0~. Do kết quả có thể rất lớn nên hãy in ra kết quả modulo ~10^9 + 7~.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên ~N~ ~(1 \le N \le 2 \times 10^5)~.

• Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ ~(0 \le a_i \le 2 \times 10^3)~.

Kết quả

In ra một số nguyên duy nhất là tích độ đẹp của tất cả bộ ba số đẹp, modulo ~10^9 + 7~.

Ví dụ

Sample Input 1

5
3 4 5 2 3

Sample Output 1

1

Sample Input 2

3
4 1 3

Sample Output 2

0

Sample Input 3

7
3 2 7 8 4 1 1

Sample Output 3

2

Chấm điểm

• Subtask 1 (20% số điểm): ~N \le 1000~.

• Subtask 2 (80% số điểm): ~N \le 2 \times 10^5~.