问题描述

健康志向的高橋君决定开始服用他在网上购买的补充剂。

一共有 $N$ 个补充剂，编号从 $1$ 到 $N$。

此外，补充剂有 $M$ 种口味，编号从 $1$ 到 $M$。第 $i$ 个补充剂（满足 $1 ≤ i ≤ N$）的口味是 $f_i$ （满足 $1 ≤ f_i ≤ M$）。

高橋君计划按照编号顺序在多天内服用补充剂。为了不懈怠，高橋君制定了以下规则：如果还剩下一个或多个补充剂，那么他必须在当天至少服用一个补充剂。

由于高橋君拥有强健的身体，他每天可以服用任意数量的补充剂，但是他会对相同口味的补充剂感到厌倦，因此他不能在同一天内服用两个或更多相同口味的补充剂。

高橋君想要在考虑补充剂的摄入方法是否合理时，知道在这种条件下总共有多少种摄取方法。

这里定义两种摄取方法不同的意思是，对于某一天来说，摄取的补充剂编号组合不同。

---

输入

从标准输入读取输入数据的格式如下：

$N$ $M$ $f_1$ $f_2$ : $f_N$

• 第 $1$ 行包含两个整数 $N (1 ≤ N ≤ 100,000)$ 和 $M (1 ≤ M ≤ 100,000)$，用空格分隔。表示一共有 $N$ 个补充剂和 $M$ 种口味。
• 第 $2$ 行到第 $N$ 行给出了关于补充剂口味的信息。其中第 $i$ 行（满足 $1 ≤ i ≤ N$）包含整数 $f_i (1 ≤ f_i ≤ M)$。表示第 $i$ 个补充剂的口味是 $f_i$。

部分分

本问题设置了部分分。

• 如果满足 $N ≤ 5,000$ 和 $M ≤ 5,000$ 的数据集 $1$ 的测试用例正确，则可以额外获得 $30$ 分。
• 如果满足附加条件的数据集 $2$ 的测试用例正确，则可以额外获得 $70$ 分。

输出

输出摄取方法的总数，对 $1,000,000,007 (= 1000000007)$ 取模，以一行形式输出。输出末尾包含换行符。

---

示例1

5 2
1
2
1
2
2

输出示例1

5

一共有 $5$ 种摄取方法。

第 $1$ 天：补充剂 $1$

第 $2$ 天：补充剂 $2$

第 $3$ 天：补充剂 $3$

第 $4$ 天：补充剂 $4$

第 $5$ 天：补充剂 $5$

或者

第 $1$ 天：补充剂 $1$

第 $2$ 天：补充剂 $2$

第 $3$ 天：补充剂 $3,4$

第 $4$ 天：补充剂 $5$

没有补充剂

或者

第 $1$ 天：补充剂 $1$

第 $2$ 天：补充剂 $2,3$

第 $3$ 天：补充剂 $4$

第 $4$ 天：补充剂 $5$

没有补充剂

或者

第 $1$ 天：补充剂 $1,2$

第 $2$ 天：补充剂 $3$

第 $3$ 天：补充剂 $4$

第 $4$ 天：补充剂 $5$

没有补充剂

或者

没有补充剂

---

示例2

6 6
1
2
3
4
5
6

输出示例2

32

无论如何摄取都不会感到厌倦。

---