人口局 DBA

题目信息

时间限制: 1s

空间限制: 256M

输入文件: dba.in

输出文件: dba.out

题目描述

T 星的每位居民都有一个唯一的正整数身份证号 $n$，T 星采用 $m$ 进制计数法。T 星的人口信息数据库系统根据 hash 函数 $S(x)$ 的值将 T 星人的个人信息分表存储，其中 $S(x)$ 的计算方式是求出 $x$ 各个位置的数字之和。

小 T 是 T 星人口局的 DBA，这天他的领导让他写一个查询代码：给定一个身份证号 $n$，求出 $x < n, S(x)=S(n)$ 的身份证号 $x$ 的数量，由于答案可能很大，且 T 星使用十进制计算机，所以只要求出答案在十进制下对 $10^9+7$ 取模的结果即可。

输入格式

第一行两个十进制正整数 $m, L$，表示 T 星采用 $m$ 进制计数法，以及测试所用身份证号 $n$ 的位数为 $L$

第二行 $L$ 个十进制正整数，表示测试所用身份证号 $n$ 从高位到低位的每一位的值，保证首位非 0

输出格式

一行一个非负整数，表示答案

样例

样例输入 1

10 3
2 1 0

样例输出 1

8

样例解释 1

201, 120, 111, 102, 30, 21, 12, 3

数据范围与提示

对于 $100 \%$ 的数据，$1 < m \leq 2000,1 \leq L \leq 2000$

• Subtask 1 (10 pts): $m, L \leq 50$
• Subtask 2 (20 pts): $S(n)<2 m$
• Subtask 3 (30 pts): $m, L \leq 500$
• Subtask 4 (40 pts)：无特殊限制