Нехай задано перестановку $a_1$, $a_2$, ..., $a_n$. Назвемо $k$-інверсією набір чисел $i_1$, $i_2$, ..., $i_k$ таких, що

$1$ ≤ $i_1$ < $i_2$ < ... < $i_k$ ≤ $n$

і

$a_{i1}$ > $a_{i2}$ > ... > $a_{ik}$.

Ваша задача - порахувати кількість різних $k$-інверсій у заданій перестановці.

Вхідні дані

У першому рядку вхідного файла знаходяться число $n$ - довжина перестановки (1 ≤ $n$ ≤ 20000), та число $k$ ($2$ ≤ $k$ ≤ $10$). У другому рядку n чисел - сама перестановка.

Вихідні дані

У вихідний файл виведіть єдине число - кількість $k$-інверсій у заданій перестановці по модулю $10^9$.