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\}$.