数口罩(Count Masks)

题目描述

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

输入格式

输入共两行：

第一行，两个正整数 $n, m$

第二行，$n$ 个正整数，其中第 $i$ 个正整数表示 $a_i$

输出格式

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

样例输入 #1

3 4
0 1 2

样例输出 #1

4

样例说明

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

样例输入 #2

4 3
0 1 1 2

样例输出 #2

0

数据范围

对于 30% 的数据，$1 \le n \le 100$

对于 70% 的数据，$1 \le n \le 10^4$

对于 100% 的数据，$1 \le n \le 10^5$，$1 \le m \le 100$

知识点与难度

本题涉及的知识点从属于 GESP 5级（组合数学、计数原理、取模运算），难度等级：⭐⭐⭐。