Рассмотрим перестановку a₁, a₂, …, a_n (все a_i — различные целые числа от 1 до n). Назовем k-инверсией последовательность индексов i₁, i₂, …, i_k такую, что 1 ≤ i₁ < i₂ < … < i_k ≤ n и a_i1 > a_i2 > … > a_ik. Вам нужно посчитать количество различных k-инверсий в заданной перестановке.

В первой строке записаны целые числа n и k (1 ≤ n ≤ 20000; 2 ≤ k ≤ 10). Во второй строке записаны целые числа a₁, …, a_n.

Выведите количество различных k-инверсий в заданной перестановке, вычисленное по модулю 10⁹.