Problem Description

Takahashi, who has a strong interest in health, decided to take supplements purchased online.

There are $ N $ supplements, numbered from $ 1 $ to $ N $.

There are also $ M $ types of flavors for the supplements, numbered from $ 1 $ to $ M $. The flavor of supplement $i\ (1\ ≦\ i\ ≦\ N)$ is $f_i\ (1\ ≦\ f_i\ ≦\ M)$.

Takahashi plans to take the supplements in order over several days. To ensure he does not slack off, he set a rule that he must take at least one supplement each day if there are any left.

Takahashi has a robust physique and can take as many supplements as he wants in a day, but he gets bored with the same flavor, so he cannot take more than one supplement of the same flavor in a single day.

Takahashi wants to evaluate the different ways he can take the supplements under these conditions and is interested in knowing how many distinct ways there are to do so.

Two ways of taking supplements are considered different if, for any day, the set of supplement numbers taken is different.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains two integers $N\ (1\ ≦\ N\ ≦\ 100,000)$ and $M\ (1\ ≦\ M\ ≦\ 100,000)$, separated by a space. This indicates there are $ N $ supplements and $ M $ types of flavors.
• The next $ N $ lines provide information about the flavors of the supplements. The $i\ (1\ ≦\ i\ ≦\ N)$th line contains an integer $f_i\ (1\ ≦\ f_i\ ≦\ M)$, indicating that supplement $ i $ has flavor $ f_i $.

Output Format

Output the total number of ways to take the supplements, modulo $1,000,000,007\ (=\ 1000000007)$, in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

5 2
1
2
1
2
2

Sample Output #1

5

Sample Input #2

6 6
1
2
3
4
5
6

Sample Output #2

32

Notes/Hints

Partial Points

This problem has partial scoring:

• If you solve the dataset where $N\ ≦\ 5,000$ and $M\ ≦\ 5,000$, you will receive an additional $ 30 $ points.
• If you solve the dataset without additional constraints, you will receive an additional $ 70 $ points.

Sample Explanation 1

There are $ 5 $ possible ways:

• Day 1: Supplement 1, Day 2: Supplement 2, Day 3: Supplement 3, Day 4: Supplement 4, Day 5: Supplement 5
• Day 1: Supplement 1, Day 2: Supplement 2, Day 3: Supplements 3,4, Day 4: Supplement 5, Day 5: None
• Day 1: Supplement 1, Day 2: Supplements 2,3, Day 3: Supplement 4, Day 4: Supplement 5, Day 5: None
• Day 1: Supplements 1,2, Day 2: Supplement 3, Day 3: Supplement 4, Day 4: Supplement 5, Day 5: None
• Day 1: Supplements 1,2, Day 2: Supplements 3,4, Day 3: Supplement 5, Day 4: None, Day 5: None

Sample Explanation 2

No matter how he eats, he will not get bored.

见题面 Input 部分

见题面 Output 部分