[ABC017D] サプリメント

### 题目描述 高桥为了健康决定网购补品。 补品有 $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)$。

[problemUrl]: https://atcoder.jp/contests/abc017/tasks/abc017_4 健康志向の高橋君は通販で購入したサプリメントを摂取することにした。 サプリメントは $ N $ 個あり、$ 1 $ から $ N $ まで番号が付けられている。 また、サプリメントの味は $ M $ 種類あり、$ 1 $ から $ M $ まで番号が付けられている。サプリメント $ i\ (1\ ≦\ i\ ≦\ N) $ の味は $ f_i\ (1\ ≦\ f_i\ ≦\ M) $ である。 高橋君はサプリメントを番号順に複数日かけて摂取する予定である。高橋君はサボらないように、サプリメントが $ 1 $ つ以上残っている場合はその日中に必ず $ 1 $ つ以上サプリメントを摂取しなければならないという規則を定めた。 高橋君は強靭な肉体を持っているため、$ 1 $ 日にどれだけサプリメントを摂取しても大丈夫だが、同じ味には飽きてしまうので、同じ日に同じ味のサプリメントを $ 2 $ つ以上摂取することはできない。 高橋君は、サプリメントの摂取方法の是非について吟味するため、このような条件下で全部で何通りの摂取方法があるかを知りたい。 ここで $ 2 $ つの摂取方法についてそれらが違うというのは、ある日について摂取したサプリメントの番号の組み合わせが異なることを定義する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ f_1 $ $ f_2 $ : $ f_N $ - $ 1 $ 行目には、$ 2 $ つの整数 $ N\ (1\ ≦\ N\ ≦\ 100,000) $ と $ M\ (1\ ≦\ M\ ≦\ 100,000) $ が空白区切りで書かれている。これはサプリメントが $ N $ 個あり、味の種類が $ M $ 種類あることを表す。 - $ 2 $ 行目から $ N $ 行には、サプリメントの味に関する情報が与えられる。これら $ N $ 行のうち上から $ i\ (1\ ≦\ i\ ≦\ N) $ 行目には整数 $ f_i\ (1\ ≦\ f_i\ ≦\ M) $ が書かれている。これは、サプリメント $ i $ の味が $ f_i $ であることを表す。

摂取方法の総数を $ 1,000,000,007\ (=\ 1000000007) $ で割ったあまりを $ 1 $ 行に出力せよ。出力の末尾にも改行を入れること。

5 2
1
2
1
2
2

5

6 6
1
2
3
4
5
6

32

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 5,000 $ かつ $ M\ ≦\ 5,000 $ を満たすデータセット $ 1 $ に正解した場合は、上記とは別に $ 30 $ 点が与えられる。 - 追加制約のないデータセット $ 2 $ に正解した場合は、上記とは別に $ 70 $ 点が与えられる。 ### Sample Explanation 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 $ なし なし ### Sample Explanation 2 どのように食べても飽きません。