There are b blocks of digits. Each one consisting of the same n digits, which are given to you in the input. Wet Shark must choose exactly one digit from each block and concatenate all of those digits together to form one large integer. For example, if he chooses digit 1 from the first block and digit 2 from the second block, he gets the integer 12.
Wet Shark then takes this number modulo x. Please, tell him how many ways he can choose one digit from each block so that he gets exactly k as the final result. As this number may be too large, print it modulo 109+7.
Note, that the number of ways to choose some digit in the block is equal to the number of it's occurrences. For example, there are 3 ways to choose digit 5 from block 3 5 6 7 8 9 5 1 1 1 1 5.
Output
Print the number of ways to pick exactly one digit from each blocks, such that the resulting integer equals
k modulo
x.
有b数字块。每个都由相同的组成n数字，在输入中给出给您。Wet Shark必须从每个块中选择一个数字，并将所有这些数字连接在一起以形成一个大整数。例如，如果他选择数字1从第一个块和数字2从第二个块，他得到整数12.
然后湿鲨鱼取这个数字模x.请告诉他他可以从每个块中选择一位数字的方法有多少种，以便他准确地得到k作为最终结果。由于此数字可能太大，请将其打印为模数109+7.
请注意，在块中选择某个数字的方法数量等于它的出现次数。例如，有3种选择数字5的方法从区块 3 5 6 7 8 9 5 1 1 1 1 5.
输入格式:
第一行有4个整数 n,b,k,x ,其中 2≤n≤50000,1≤b≤109,0≤k<x≤100,x≥2 第二行有 n 个数, 为每个格子里面的数字(每个格子里面的数字都是相同的.)
输出格式:
即从每个块中选择一个数构成一个大数, 使得其模x为k的方案数对 1×109+71×109+7 取模. 注意:
样例二中没有一种方案使得模2为1 样例三中11,13,21,23,31,33满足模2余1.
Note
In the second sample possible integers are
22,
26,
62 and
66. None of them gives the remainder
1 modulo
2.
In the third sample integers
11,
13,
21,
23,
31 and
33 have remainder
1 modulo
2. There is exactly one way to obtain each of these integers, so the total answer is
6.