题目描述

有 $n$ 名学生排成了一列长队，每名学生都戴口罩，口罩的式样共有 $m$ 种。每一名学生都比较关心排在他前面的学生中，有多少人带的口罩式样和他是相同的。设 $a_i$ 表示在第 $i$ 名学生前的 $i-1$ 名学生中，有 $a_i$ 名学生戴的口罩式样与他一模一样，请问有多少种不同的排队方案，能够使得与给定数据一致？

输入格式

输入共两行： 第一行，两个正整数$n,m$ 第二行，$n$个正整数，其中第$i$个正整数表示$a_i$

输出格式

输出一个正整数，表示可能的方案数对$1e9+7$取模后的结果，若不可能出现输入的情况，则输出$0$

3 4
0 1 2

4

样例解释 1

对于给定输入，可以推出每个人和前一个人所带口罩颜色均相同，所以可能的情况共有4种：

1. 每个人都带颜色1的口罩
2. 每个人都带颜色2的口罩
3. 每个人都带颜色3的口罩
4. 每个人都带颜色4的口罩

4 3
0 1 1 2

0

样例解释 2

第一个人和第二个人所带口罩颜色相同，但第三个人前面有一个与他颜色相同，产生矛盾，不可能发生这种情况，故方案数为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$