拼接碎片

数列推演完了，但Echo-0留下的不只是数列——还有碎片。无数的碎片，散落在数学空间里。

"碎片？"CC问。

"对。"Echo说，"每块碎片上有一个数。我们要把它们拼起来。"

"拼成啥？"

"一个完整的数。"你说，"给定$n$块碎片，每块上面有一个数$a_i$。我们要选一些碎片，把它们拼接起来，使得拼接后的数模$m$等于0。"

"拼接？"

"对。"你说，"比如23和45，拼接成2345。"

"咋选？"

"状态压缩。"你说，"每块碎片用一位二进制表示——选或不选。$2^n$种状态。"

"$n$多大？"

"不超过15。"你说，"$2^{15}=32768$，可以接受。"

"拼接后的数会很大吧？"

"对。"你说，"所以全程模$m$。拼接时，先乘10的位数幂，再加新数。"

"比如？"

"比如已有数$x$，拼接$y$（$y$有$d$位），新数是$x\times 10^d+y$。"

"模$m$后？"

"$(x\times 10^d+y)\bmod m$。"你说，"每一步都取模，数字不会溢出。"

"第47块碎片。"你说，"选它。"

"47？"

"对。"你说，"47。"

CC把第47块碎片捡回来——上面写着一个"1"。

"1？"

"对。"她说，"1。"

"1是最小的数。"你说，"但也是最重要的——所有数都从1开始。"

Echo看着碎片一块一块拼起来——像拼图，像记忆，像某种被时间打碎的东西重新聚合。

"以前这些碎片是乱的。"她说，"现在……有顺序了。"

"因为有我们。"你说。

"对。"她说，"因为有你们。"

题目描述

给定$n$个数$a_i$，每个数有$d_i$位。选一些数拼接起来，使得结果模$m$为0。求方案数。

输入格式

第一行$n$和$m$。接下来$n$行，每行一个数$a_i$。

输出格式

方案数模$10^9+7$。

输入样例

5

输出样例

0

提示

• 状态压缩DP：$dp[mask][r]$表示选了$mask$中的数，当前余数为$r$的方案数。
• 转移：枚举下一块碎片，$dp[mask|bit][(r\times 10^{d_i}+a_i)\bmod m]+=dp[mask][r]$。
• $n\le 15$，$2^n\times m$可接受。