Вам задано послідовність цілих чисел \(A = (A_1, \dots, A_N\)) довжини \(N\).

Знайдіть число за модулем 998244353 перестановок \(P = (P_1, \dots, P_N)\) з (\(1, 2, \dots, N\)) так, що:

• існує рівно \(K\) цілих чисел \(i\) між 1 і (\(N-1\)) (включно), таких що \(A_{P_i} \lt A_{P_{i + 1}}\).

Обмеження

• \(2 \leq N \leq 5000\)
• \(0 \leq K \leq N - 1\)
• \(1 \leq A_i \leq N\, (1 \leq i \leq N)\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N,K\)

Наступний  рядок містить \(N\) цілих чисел \(A_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть відповідь.

Примітка

До прикладу 1:

P=(1,3,2,4),(1,4,2,3),(2,3,1,4),(2,4,1,3).

Приклад вхідних даних

4 2
1 1 2 2

Приклад вихідних даних

4

Приклад вхідних даних

10 3
3 1 4 1 5 9 2 6 5 3

Приклад вихідних даних

697112