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 * q\) với mọi \(1 \leq i < k\).

Yêu cầu

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 thiết bị ra chuẩn 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)\).

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.

Example

5 2
1 2 8 4 2

3 1 0 0