AT_abc017_4.[ABC017D] サプリメント

健康志向的高桥君决定服用通过网购购买的保健品。

共有 $N$ 个保健品，编号从 $1$ 到 $N$。

保健品的口味有 $M$ 种，编号从 $1$ 到 $M$。第 $i$ 个保健品的口味为 $f_i$，其中 $1 \leq f_i \leq M$。

高桥君打算按照编号顺序，在多天内依次服用这些保健品。为了防止偷懒，他规定只要还有剩余的保健品，每天必须至少服用一个。

高桥君身体强壮，每天可以服用任意数量的保健品，但同一天内不能服用两种相同口味的保健品，因为会吃腻。

高桥君想知道，在上述条件下，总共有多少种不同的服用方式。

这里，若存在某一天所服用的保健品编号的组合不同，则认为两种服用方式不同。

输入通过标准输入给出，格式如下：

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

• 第 $1$ 行包含两个整数 $N\ (1 \leq N \leq 100,000)$ 和 $M\ (1 \leq M \leq 100,000)$，分别表示保健品的数量和口味的种类数。
• 接下来的 $N$ 行，每行一个整数 $f_i\ (1 \leq f_i \leq M)$，表示第 $i$ 个保健品的口味。

输出服用方式的总数对 $1,000,000,007\ (=1000000007)$ 取模的结果。输出末尾需换行。

部分分

本题设有部分分。

• 若能通过 $N \leq 5,000$ 且 $M \leq 5,000$ 的数据集 $1$，可获得 $30$ 分。
• 若能通过无额外限制的数据集 $2$，可获得 $70$ 分。

样例解释 1

以下是 $5$ 种可能的服用方式：

第 1 天	第 2 天	第 3 天	第 4 天	第 5 天
保健品 1	保健品 2	保健品 3	保健品 4	保健品 5
保健品 1	保健品 2	保健品 3,4	保健品 5	无
保健品 1	保健品 2,3	保健品 4	保健品 5	无
保健品 1,2	保健品 3	保健品 4	保健品 5	无
保健品 1,2	保健品 3,4	保健品 5	无	无

样例解释 2

无论如何服用都不会吃腻。

由 ChatGPT 4.1 翻译