题目背景

春日镇有家很受欢迎的小便利店，收银台旁有一块木制数字牌。为了不让排队的人心情变糟，店长想出个小游戏： 每张小票上都会印一个“好心情编号”——这是一串用 m 种符号写成的数字（也就是 m 进制），每一位的符号都被赋予了从 0 到 m−1 的“愉悦值”。整串编号的“好心情值”就等于所有位上愉悦值的总和。

某天，店长想统计：对某张小票的编号 $n$ 来说，有多少个更早开出的编号（按 m 进制的数值比较，小于 $n$），它们的“好心情值”和 $n$ 一样？为了方便对账，最后只需要把答案用十进制输出，并对 $10^9+7$ 取模。

你需要扮演店员小春，写出这次统计的结果。

题目描述

给定一个采用 m 进制表示的正整数编号 $n$。定义

求满足 $x<n$ 且 $S(x)=S(n)$ 的编号个数。答案在十进制下对 $10^9+7$ 取模。

输入格式

• 第一行：两个十进制正整数 $m, L$，表示编号使用的进制为 $m$；编号 $n$ 的位数为 $L$。
• 第二行：给出 $L$ 个十进制正整数，为编号 $n$ 从高位到低位的每一位在 $[0, m-1]$ 内的数值，且保证首位非 0。

输出格式

输出一行一个非负整数，表示满足条件的编号个数（十进制，模 $10^9+7$）。

样例

样例输入 1

10 3
2 1 0

样例输出 1

8

样例解释 1

与 $210$（十进制书写，仅为展示）拥有相同“好心情值”且更小的编号共有 8 个： 201, 120, 111, 102, 30, 21, 12, 3。

数据范围与温馨提示

• 对于 $100\%$ 的数据：$1 < m \le 2000,\; 1 \le L \le 2000$。
• 输入中的所有数字都用十进制给出，只是它们表达的是一个 m 进制的编号。

部分分

• Subtask 1（10 分）： $m, L \le 50$

• Subtask 2（20 分）： 满足 $S(n) < 2m$

• Subtask 3（30 分）： $m, L \le 500$

• Subtask 4（40 分）： 无特殊限制