CF621E Wet Shark and Blocks

有 $b$ 个格子，每个格子有 $n$ 个数字，各个格子里面的数字都是相同的. 求从 $b$ 个格子中各取一个数字, 构成一个 $b$ 位数, 使得这个 $b$ 位数模 $x$ 为 $k$ 的方案数（同一格子内相同的数字算不同方案）.答案对 $1\times 10^9+7$ 取模.

第一行有4个整数 $n,b,k,x$ ,其中 $2\leq n\leq 50000,1\leq b\leq 10^{9},0\leq k< x\leq 100,x\ge2$ 第二行有 $n$ 个数, 为每个格子里面的数字(每个格子里面的数字都是相同的.)

即从每个块中选择一个数构成一个大数, 使得其模x为k的方案数对 $1\times 10^9+7$ 取模. 注意: 样例二中没有一种方案使得模2为1 样例三中11,13,21,23,31,33满足模2余1. 感谢@aiyougege 提供的翻译

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