THỰC HÀNH

(Đề đề xuất DHBB 2017 của THPT CHUYÊN HÙNG VƯƠNG PHÚ THỌ)

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.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương n là số cây đũa.
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n là các số ghi trên các cây đũa, hai số liên tiếp được ghi cách nhau một dấu cách.

Dữ liệu ra:

            Một số nguyên duy nhất là phần dư của số cách chọn khi chia cho 1000000007.

Ví dụ:

Dữ liệu vào:
5
1 3 3 9 27
Dữ liệu ra:
4

Giải thích: Harry Potter có thể chọn các bộ 3 số sau: (a₁, a₂, a₄) = (1, 3, 9), (a₁, a₃, a₄) = (1, 3, 9), (a₂, a₄, a₅) = (3, 9, 27), (a₃, a₄, a₅) = (3, 9, 27). Tổng cộng có 4 cách.

Giới hạn: 1 ≤ n ≤ 10⁵; | a_i |≤ 10⁹.