Tu ești patronul unei echipe de fotbal. Ai găsit strategia perfectă pentru a câștiga orice meci pe care îl va juca echipa ta. Strategia aceasta constă în a spune fiecărui jucător de a da pase la exact o persoană. Chiar dacă inițial pare o strategie proastă, aceasta te a ajutat să ajungi până în finala campionatului pe sate.

Într-o echipa se formează alte "sub-echipe". O "sub-echipă" reprezintă o mulțime de jucători în care orice jucător poate da pase oricărui alt jucător printr-o pasă indirectă sau o serie de pase. În aceste "sub-echipe" ai stabilit anumite roluri pe care minim un jucător trebuie sa aibă, mai exact $K$ roluri diferite.

Cerință

Știind că sunt $N$ jucători în echipă, $K$ roluri diferite și fiecare pasă pe care o poate face un jucător, să se afle numărul de moduri în care se pot da roluri echipei.

Date de intrare

Pe prima linie a fișierului de intrare echipe.in se află $N$ urmat de $K$. Pe următoarea linie se află un șir de numere naturale $p_1$, $p_2$, $\cdots$ , $p_N$ .
Pentru fiecare $i$, $1 \leq i \leq N$, jucătorul $i$ poate să dea pase jucătorului $p_i$.

Date de ieșire

Pe prima linie a fișierului de ieșire echipe.out se va găsi un singur număr întreg, care reprezintă restul împărțirii la $10^9 + 7$ a numărului de moduri de a da roluri echipei

Restricții și precizări

• $1 \leq K \leq N \leq 2 \cdot 10^5$
• Fiecare numar din intervalul $[1, N]$ apare în șirul $p$ apare decât o dată
• Se asigură faptul că există cel puțin un mod de a da roluri echipei

Subtask-uri

Exemplu

echipe.in

5 2
2 3 1 5 4

echipe.out

12

Explicație

Sub-echipele formate sunt: $\{ \texttt{1, 2, 3} \}$ si $\{ \texttt{4, 5} \}$

Iar așa arată pasele pe care le vor face jucătorii, iar modurile în care se pot da roluri sunt următoarele ($r_i$ indică rolul jucătorului $i$) :