Cho dãy gồm \(n\) số nguyên dương \(A = (a_1, a_2, \ldots, a_n)\).
Dãy số \(b_1, b_2, \ldots, b_k\) được gọi là dãy cấp số nhân công bội \(q\) khi và chỉ khi \(b_{i+1} = b_i \cdot q\) với mọi \(1 \le i < k\).

Yêu cầu: Cho số nguyên \(q\), với mỗi \(k\) (\(1 \le k \le n\)), hãy đếm số dãy con (không nhất thiết liên tiếp) độ dài \(k\) của dãy \(A\) là dãy cấp số nhân công bội \(q\).

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\).

Output

• Ghi ra thiết bị ra chuẩn một dòng gồm \(n\) số nguyên, số thứ \(k\) là số dãy con độ dài \(k\) là dãy cấp số nhân công bội \(q\) chia dư cho \(10^9 + 7\).

Example

5 2
1 2 8 4 2

5 3 1 0 0

Ràng buộc

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 20\);
• \(25\%\) số test khác ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 1000\);
• \(25\%\) số test khác ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 10^5, q = 1\);
• \(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. (\(a_i \le 10^9\))