Kazak Vus və rənglər

Giriş

Birinci sətir iki tam ədəd $n$ və $k$ ( $1 \leq n \leq 5 \cdot 1 0^{5}, 3 \leq k \leq 1 0^{9}$ 1 \le n \le 5 \cdot 10^5, 3 \le k \le 10^9) — daşların sayı və rənglərin sayı.

İkinci sətir $n$ tam ədəd $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $0 \leq a_{i} \leq k$ 0 \le a_i \le k) — daşların rəngləri. Əgər $a_{i} = 0$ a_i=0, bu o deməkdir ki, müvafiq daş hələ boyanmayıb. Əgər $1 \leq a_{i} \leq k$ 1 \le a_i \le k, bu o deməkdir ki, daş $a_{i}$ a_i nömrəli rənglə boyanıb.

Çıxış

Tək bir ədəd çıxarın — daşların boyanma üsullarının $1 0^{9} + 7$ 10^9+7-yə bölünmədən qalanı.

Nümunələr

Nümunə 1

Loading

Nümunə 2

Loading

Nümunə 3

Loading

Bal hesablama

( $12$ bal): $n, k \leq 7$ n, k \le 7;
( $11$ bal): $n, k \leq 200, a_{i} = 0$ n, k \le 200, a_i=0;
( $23$ bal): $n, k \leq 200$ n, k \le 200;
( $25$ bal): $n, k \leq 3000$ n, k \le 3000;
( $29$ bal): əlavə məhdudiyyətlərsiz.