Cho dãy gồm 𝑛 số nguyên dương 𝑎₁, 𝑎₂, … , 𝑎_𝑛. Dãy số 𝑏₁, 𝑏₂, … , 𝑏_𝑘 được gọi là dãy cấp số nhân công bội 𝑞 khi và chỉ khi 𝑏_𝑖+1 = 𝑏_𝑖 × 𝑞 với mọi 1 ≤ 𝑖 < 𝑘.

Yêu cầu: Cho số nguyên 𝑞, với mỗi 𝑘 (1 < 𝑘 ≤ 𝑛), hãy đếm số dãy con (không nhất thiết liên tiếp) độ dài 𝑘 của dãy 𝑎₁, 𝑎₂, … , 𝑎_𝑛 là dãy cấp số nhân công bội 𝑞.

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên 𝑛, 𝑞 (1 ≤ 𝑛 ≤ 10⁵, 2 ≤ 𝑞 ≤ 10⁹);

• Dòng thứ hai chứa 𝑛 số nguyên 𝑎₁, 𝑎₂, … , 𝑎_𝑛(1 ≤ 𝑎_𝑖 ≤ 10⁹).

Kết quả: Ghi một dòng gồm 𝑛 − 1 số nguyên, số thứ 𝑠(1 ≤ 𝑠 < 𝑛) là số dãy con độ dài 𝑠 + 1 là dãy cấp số nhân công bội 𝑞 chia dư cho (𝟏𝟎^𝟗 + 𝟕).

Ràng buộc:

• Có 25% số test ứng với 25% số điểm của bài thỏa mãn: 𝑛 ≤ 20;

• 25% số test khác ứng với 25% số điểm của bài thỏa mãn: 𝑛 ≤ 100;

• 25% số test khác ứng với 25% số điểm của bài thỏa mãn: 𝑛 ≤ 1000;

• 25% số test còn lại ứng với 25% số điểm của bài không có ràng buộc gì thêm.

Ví dụ: