题目描述
有 $n$ 名学生排成了一列长队，每名学生都戴口罩，口罩的式样共有 $m$ 种。每一名学生都比较关心排在他前面的学生中，有多少人带的口罩式样和他是相同的。设 $a_i$ 表示在第 $i$ 名学生前的 $i-1$ 名学生中，有 $a_i$ 名学生戴的口罩式样与他一模一样，请问有多少种不同的排队方案，能够使得与给定数据一致？
输入
输入共两行：
第一行，两个正整数$n,m$
第二行，$n$个正整数，其中第$i$个正整数表示$a_i$
输出
输出一个正整数，表示可能的方案数对$1e9+7$取模后的结果，若不可能出现输入的情况，则输出$0$
样例输入输出
提示
对于$30\%$的数据，$1 \leq n \leq 100$
对于$70\%$的数据，$1 \leq n \leq 10^4$
对于$100\%$的数据，$1 \leq n \leq 10^5$ ，$1 \leq m \leq 100$
样例1说明:对于给定输入，可以推出每个人和前一个人所带口罩颜色均相同，所以可能的情况共有4种：
1. 每个人都带颜色1的口罩
2. 每个人都带颜色2的口罩
3. 每个人都带颜色3的口罩
4. 每个人都带颜色4的口罩
样例2说明:第一个人和第二个人所带口罩颜色相同，但第三个人前面有一个与他颜色相同，产生矛盾，不可能发生这种情况，故方案数为0