题目描述

高桥为了健康决定网购补品。

补品有 $N$ 个，编号为 $1$ 到 $N$。

另外，补品的味道有 $M$ 类，编号为 $1$ 到 $M$。补品 $i (1 \leqslant i \leqslant N)$ 的味道是 $f_i (1 \leqslant f_i \leqslant M)$。

高桥打算按照顺序多日摄取补品。他为了不偷懒，制定了如果剩下 $1$ 个以上的补品的话，当天必须摄取 $1$ 个以上的补品的规则。

因为高桥有着健康的身体，所以 $1$ 日摄取多少补品都没关系，但是因为他会对同样的味道感到厌倦，所以他不能在同一天摄取 $2$ 个以上同样味道的补品。

高桥想知道在这样的条件下一共有多少种摄取方法。将方案数对 $10^9 + 7$ 取模后输出。

这里，关于两种不同的摄取方法的定义是，某一天摄取的补品的编号组合不同。

输入格式

输入以以下形式给出。

$N M f_1\ f_2​ : f_N$

在第 $1$ 行中，以空白分隔写有 $2$ 个整数 $N (1 \leqslant N \leqslant 10^5)$ 和 $M (1 \leqslant M \leqslant 10^5)$。表示补品有 $N$ 个，共有 $M$ 种。 从第 $2$ 行到第 $N$ 行提供关于补品的味道的信息。在以下 $N$ 行中，第 $i (1 \leqslant i \leqslant N)$ 行是整数 $f_i (1 \leqslant f_i \leqslant M)$。