K-inversiyalar

Verilmiş $a_1$, $a_2$, ..., $a_n$ permutasiyası üçün $k$-inversiya adlanan ədədlər dəstini $i_1$, $i_2$, ..., $i_k$ kimi təyin edək ki,

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

və

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

Sizin vəzifəniz, verilmiş permutasiyada müxtəlif $k$-inversiyaların sayını hesablamaqdır.

Giriş məlumatları

Girişin ilk sətirində $n$ - permutasiyanın uzunluğu (1 ≤ $n$ ≤ 20000) və $k$ ($2$ ≤ $k$ ≤ $10$) ədədləri verilir. İkinci sətirdə isə permutasiyanın özünü təşkil edən $n$ ədəd verilir.

Çıxış məlumatları

Çıxışda, verilmiş permutasiyada $k$-inversiyaların sayını $10^9$ modulu ilə tək bir ədəd kimi yazın.

Nümunələr