题目描述

Aki 面前有 $b$ 块数字积木。

每一块积木上都写着完全相同的 $n$ 个数字，记为 $a_1,a_2,\dots,a_n$。
Aki 需要从第 $1$ 块到第 $b$ 块中，每块恰好选出一个数字，并按顺序拼接成一个长度为 $b$ 的十进制整数。

例如，若从前两块中依次选出数字 $1,2$，那么前两位就组成了整数 12。

现在 Aki 会把这个整数对 $x$ 取模。你需要求出：有多少种选法，能够使最终结果恰好等于 $k$。

由于答案可能很大，请对 $10^9+7$ 取模输出。

• 每一块积木上的数字内容完全相同；
• 如果某个数字在一块积木中出现了多次，那么选择它的不同位置要算作不同方案；
• 输入保证 $1\le a_i\le 9$。

输入格式

第一行四个整数 $n,b,k,x$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每一块积木上写着的数字。

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

输出格式

输出一个整数，表示满足条件的方案数，对 $10^9+7$ 取模后的结果。

12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5

3

Hint

样例解释： 这里只有一块积木，因此最后得到的数就是你选出的那个数字本身。 想要模 $10$ 后得到 $5$，就必须选到数字 $5$。
而这一块积木中一共有 $3$ 个位置写着数字 $5$，所以答案为 $3$。