Sau khi trường Hogwarts bị ám bởi lời nguyền của Voldemort. Tất cả các đũa phép ở trường Hogwarts bị biến dạng, mỗi chiếc đũa phép bị in một số lạ trên đũa. Thầy hiệu trưởng Dumbledore mới ra lệnh cho tất cả học sinh tập trung tại sảnh và yêu cầu tất cả mọi người đặt những chiếc đũa thành một hàng ngang. Để giải được lời nguyền đầu tiên phải biến những chiếc đũa phép trở lại bình thường. Vì hiểu rõ cách hoạt động của lời nguyền, thầy Dumbledore yêu cầu các học sinh chọn ra 3 chiếc đũa, nếu 3 con số trên đũa theo thứ tự là một cấp số nhân với công bội là 3 thì chúng sẽ lập tức trở lại bình thường.

Harry được các bạn cử lên là người đầu tiên thực hiện, hỏi Harry sẽ có bao nhiêu cách chọn.

Yêu cầu: Cho một dãy số có ~n~ số nguyên ~a_i~, đếm số lượng bộ số ~i < j < k~ sao cho theo thứ tự chúng là một cấp số nhân với công bội 3.

Input

• Dòng đầu chứa số nguyên dương ~n~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~.

Output

• Một dòng duy nhất là kết quả của bài toán lấy dư cho ~10^9 + 7~.

Sample Input 1

5
1 3 3 9 27

Sample Output 1

2