Khối chữ số modulo

Cho $b$ khối, mỗi khối chứa cùng $n$ chữ số (nằm trong khoảng $1$ đến $9$) được cho trong dữ liệu vào.

Bạn phải chọn đúng một chữ số từ mỗi khối, rồi ghép các chữ số đã chọn theo thứ tự khối thành một số nguyên lớn. Hãy đếm số cách chọn sao cho số nguyên thu được chia $x$ dư đúng $k$. Vì kết quả có thể rất lớn, hãy in nó theo modulo ${10}^9+7$.

Hai cách chọn được coi là khác nhau nếu tại một khối nào đó, vị trí của chữ số được chọn trong khối là khác nhau (kể cả khi giá trị của chữ số trùng nhau). Ví dụ, khối $356789511115$ có ba cách chọn chữ số $5$ (vì chữ số $5$ xuất hiện ba lần).

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n$, $b$, $k$, $x$ cách nhau bởi dấu cách.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — các chữ số trong mỗi khối.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách chọn thoả mãn, lấy modulo ${10}^9+7$.

Ràng buộc

• $2\le n\le 50000$
• $1\le b\le {10}^9$
• $0\le k<x\le 100$, $x\ge 2$
• $1\le a_i\le 9$

Ví dụ