Cho \(S\) là một tập hợp các số tự nhiên, số nguyên dương \(m\) và số tự nhiên \(r\) \((0 \le r < m)\); đếm số lượng tập con phân biệt của \(S\) (trừ tập rỗng) mà tích các phần tử trong mỗi tập con đó chia cho \(m\) có số dư là \(r\).

Đầu vào

Dòng đầu chứa số tự nhiên \(n\) \((1 \le n \le 1000)\).

Dòng tiếp theo chứa hai số tự nhiên \(m\) \((1 \le m \le 1000)\) và \(r\) \((0 \le r < m)\).

Dòng cuối cùng gồm \(n\) số tự nhiên trong đoạn \([0, 10^{9}]\) là các phần tử của tập hợp.

Ghi chú: \(n\) số tự nhiên nhập vào đảm bảo đôi một phân biệt.

Đầu ra

Một số tự nhiên duy nhất là số lượng tập con cần tìm.

Chú ý: Kết quả lấy mod không âm cho \(10^9 + 7\).

Ví dụ

Đầu vào:

4
3 2
1 2 3 4

Đầu ra:

4

Giải thích: 4 tập con của \(\{1, 2, 3, 4\}\) có tích các phần tử chia 3 dư 2 là: \(\{2\}\), \(\{1, 2\}\), \(\{2, 4\}\), \(\{1, 2, 4\}\).