Cho dãy gồm n số nguyên dương \(a_1, a_2, ... a_n\). Dãy số \(b_1, b_2, ... 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 \times q\) với mọi \(1 \le i \lt k\).

Yêu cầu: Cho số nguyên \(q\), với mỗi \(k (1 \lt 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_1, a_2, ... a_n\) là dãy cấp số nhân công bội \(q\).

Dữ liệu:

• Dòng đầu tiên gồm hai số nguyên \(n, q (1 \le n \le 10^5; 2 \le q \le 10^9)\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n (1 \le a_i \le 10^9)\)

Kết quả: Một dòng gồm \(n-1\) số nguyên, số thứ \(s (1 \le s \lt n)\) là số dãy con độ dài \((s+1)\) là dãy cấp số nhân công bội \(q\) chia dư cho \((10^9 + 7)\)

Ràng buộ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 ứng với 25% số điểm của bài thỏa mãn: \(n \le 100\)
• 25% số test ứng với 25% số điểm của bài thỏa mãn: \(n \le 1000\)
• 25% số test ứng với 25% số điểm của bài không có ràng buộc gì thêm

Input

5 2
1 2 8 4 2

Output

3 1 0 0