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 翻译