bin9638, em trai Hùng Bá, cũng là một tay định giá thứ thiệt. Khác với anh mình chuyên định giá tiền thì bin9638 lại chuyên định giá những que diêm. Ở nhà của anh có rất nhiều que diêm, từ diêm có gỗ được lấy từ những cây gỗ quý từ rừng rậm Amazon, diêm cổ \(1000\) tuổi, diêm được mạ vàng,....

Một hôm vì thấy định giá diêm mãi cũng chán nên bin9638 nghĩ ra trò mới với những que diêm của mình. bin9638 bắt đầu dùng những que diêm của mình để xếp hình, anh bắt đầu với hình mình thích nhất là hình chữ nhật. Hiện tại bộ sưu tầm diêm của bin9638 có \(n\) que diêm có độ dài \(A_1, A_2, A_3, .... A_n\) \(( 1 \le A_i \le 10^9 )\), anh ấy muốn biết là với bộ sưu tầm này thì có thể chọn ra bao nhiêu bộ \(4\) que diêm để chúng có thể tạo thành hình chữ nhật.

bin9638 cứ xếp mãi vẫn chưa xong, nên bây giờ anh ấy muốn nhờ các bạn chuyên tin giải giúp. Nếu giúp thành công thì còn được bin9638 tặng \(1\) que diêm mạ inox nữa nhé !

Input

• Dòng đầu tiên là số \(n\).
• Dòng tiếp theo là dãy \(A\).

Output

• \(1\) số duy nhất là phần dư của kết quả khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 300\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 3000\).
• Subtask \(4\) (\(40\%\) số điểm): \(n \le 2*10^5\).

Example

6
1 2 1 2 1 3

3