Bob 的妹妹 Alice 今年九岁。Bob 用计算一个数除以 9 的余数来考查她。
今天 Bob 提出了 N 个问题,编号为 0 到 N-1。每个问题给出的都是同一个 M 位数字串,允许含前导零。Alice 在读数时可能跳过部分数位,但计算余数时不会出错。
例如 Bob 连续三次给出 012345,Alice 可能分别读成 0145、012345 和 135,对应除以 9 的余数分别为 1,6,0。
给定长度为 M 的数组 d,下标为 0 到 M-1。d_i 对应原数字串中权值为 10^i 的数位。当且仅当 d_i 的二进制第 j 位为 1 时,Alice 在回答第 j 个问题时读到了第 i 个数位。二进制位从最低位起编号为 0。
例如 d_3=6=(110)_2,表示 Alice 在问题 0 中跳过这个数位,在问题 1,2 中读到这个数位。保证每个问题至少读到一个数位。
这次所有 N 个问题的余数都为 0。请计算有多少个允许前导零的 M 位数字串符合条件,答案对 10^9+7 取模。不同数位上的数字不同,就视为不同数字串。
第一行一个整数 N。第二行一个整数 M,即数组 d 的长度。第三行 M 个整数 d_0,d_1,\ldots,d_{M-1},以空格分隔。
输出一行一个整数,表示合法数字串个数对 10^9+7 取模的结果。
2 2 1 2
4
2 2 3 3
12
2 3 1 3 2
16