Cho dãy gồm \(n\) số nguyên \(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 \cdot q\) với mọi \(1 \leq i < k\).

Cho số nguyên \(q\), với mỗi \(k\) \((1 < k \leq 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\).

Input

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

Output

• Ghi ra một dòng gồm \(n - 1\) số nguyên, số thứ \(s\) \((1 \leq s < 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)\).

Example

5 2
1 2 8 4 2

3 1 0 0

Scoring

• Có \(25\%\) số điểm của bài toán thỏa mãn \(n \leq 20\).
• Có \(25\%\) số điểm của bài toán thỏa mãn \(n \leq 100\).
• Có \(25\%\) số điểm của bài toán thỏa mãn \(n \leq 1000\).
• Có \(25\%\) số điểm của bài toán không có ràng buộc gì thêm.