Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
G. Making Records
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
II. Allegro
Shostakovich, Symphony No. 10

John is making $$$n$$$ records and he knows of $$$m$$$ unique songs. Each record must contain exactly one song. Further, each record has a value $$$b_i$$$ denoting that if the $$$i$$$th record is played, the $$$b_i$$$th record must be played next. John can assign any song to any record (there may be multiple records with the same song, or a song that isn't on any record), but each record must be assigned exactly one song. However, he wants to make sure that anyone who plays his records will not end up listening to the same song twice.

Formally, let $$$a_i$$$ be the song assigned to the $$$i$$$th record. For all $$$i$$$, $$$a_i \neq a_{b_i}$$$ must hold. Help John determine how many assignments of songs to records satisfy this condition. Two assignments are considered different if there is a record which has a different song assigned to it between the two assignments. Since this value may be large, output it modulo $$$10^9+7$$$.

Input

The first line of input will contain integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — the number of records and the number of song choices, respectively.

The next line of input will contain $$$n$$$ space-separated integers $$$b_1 ... b_n$$$ ($$$1 \leq b_i \leq n$$$) — the record that must be played directly after the $$$i$$$th record.

Output

Output the number of valid assignments, modulo $$$10^9+7$$$.

Examples
Input
5 3
2 3 4 1 4
Output
36
Input
2 1
2 1
Output
0
Input
2 1
1 2
Output
0
Input
8 10
4 3 6 2 3 7 1 2
Output
43047450
Note

In the first sample, the 2nd record must be played after the first, the third record must be played after the second, the fourth must be played after the third, the first after the fourth, and the fourth after the fifth. This means that records 1, 2, 3, and 4 will cycle infinitely, and record 5 will only be played once if it is the first record played. An example of a valid assignment of songs to records is to assign song 1 to records 1 and 3, song 2 to records 2 and 5, and song 3 to record 4. Notice that with this assignment there were never be a song that is played twice in a row. It can be shown that there are exactly 36 assignments which satisfy this condition in this testcase.

In the second sample, there is only one song, so there is only one way to assign songs to records, but because record 2 is played after record 1, this assignment is invalid.

In the third sample, record 1 is played after itself, so all assignments of songs to records will be invalid.