Naturalne podciągi

Limit czasu: 0.5s | Limit pamięci: 32MB

Dla danego ciągu $a_1, a_2, \ldots, a_n$ i liczby $k$ wyznacz liczbę jego niekoniecznie spójnych podciągów równych $1, 2, \ldots, k$.

Wejście

Pierwszy wiersz zawiera liczby $n$ i $k$ oddzielone spacją. Drugi wiersz zawiera $n$ liczb $a_i$ odzielonych spacjami.

Wyjście

Pierwszy wiersz powinien zawierać jedną liczbę oznaczającą liczbę podciągów równych $1, 2, \ldots, k$ modulo $10^9+7$.

Ograniczenia

• $1 \le n, k, a_i \le 200\,000$

Przykład

Wejście 1

7 3
1 2 7 3 2 5 3

Wyjście 1

3