有 b 组数字。每个数字都包含相同的 n 位数字,这些数字是在输入中提供给您的。 Wet Shark 必须从每个块中准确选择一位数字,并将所有这些数字连接在一起形成一个大整数。例如,如果他从第一个块中选择数字 1,从第二个块中选择数字 2,则他得到整数 12。
Wet Shark 然后用这个数字对 x 取模。请告诉他有多少种方法可以从每个块中选择一位数字,以便他准确地得到 k 作为最终结果。由于该数字可能太大,因此将其打印为 109 + 7 模。
请注意,在块中选择某个数字的方式数等于它出现的次数。例如,有3种方法可以从块3 5 6 7 8 9 5 1 1 1 1 5中选择数字5。
输入
输入的第一行包含四个空格分隔的整数 n、b、k 和 x (2 ≤ n ≤ 50 000, 1 ≤ b ≤ 109, 0 ≤ k < x ≤ 100, x ≥ 2) - 一个块中的位数、块的数量、模 x 的有趣余数和模 x 本身。
下一行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 9),它们给出每个块中包含的数字。
输出
打印从每个块中精确选取一位数字的方法数,使得所得整数等于 k 模 x。
示例
输入 #1
12 1 5 10 3 5 6 7 8 9 5 1 1 1 1 5
输出 #1
3
输入 #2
3 2 1 2 6 2 2
输出 #2
0
输入 #3
3 2 1 2 3 1 2
输出 #3
6
注意
在第二个样本中,可能的整数为 22、26、62 和 66。它们都不能给出 1 模 2 的余数。
在第三个样本中,整数 11、13、21、23、31 和 33 的余数为 1 模 2。只有一种方法可以获得这些整数,因此总答案为 6。