hanoi

Un tânăr elev vietnamez a cumpărat de la magazin $N$ discuri. Pe fiecare disc este o etichetă pe care este scris diametrul acestuia exprimat în cm.

Tânărul vrea să așeze, în toate modurile posibile, cele $N$ discuri pe $K$ tije (numerotate de la $1$ la $K$), astfel încât, pe fiecare tijă, discurile să fie ordonate după diametru strict crescător, de la vârf la bază. În plus, nicio tijă nu trebuie să rămână liberă.

Două moduri de așezare sunt considerate distincte dacă există cel puțin o tijă pentru care valorile de pe etichetele discurilor așezate pe tija respectivă diferă în cele două așezări.

De exemplu, dacă avem $N = 3$ discuri cu diametrele $1 \ 1 \ 3$, acestea pot fi așezate pe $K = 2$ tije în două moduri distincte:

Cerință

Scrieți un program care, cunoscând $N$, $K$, precum și diametrele celor $N$ discuri, determină numărul de moduri distincte de așezare a discurilor în condițiile din enunț (modulo $99041$).

Date de intrare

Fișierul de intrare hanoi.in conține pe prima linie numerele naturale $N$ și $K$, având semnificația din enunț. Pe cea de a doua linie se află $N$ numere naturale reprezentând diametrele celor $N$ discuri. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire hanoi.out conține o singură linie pe care este scris rezultatul cerut.

Restricții și precizări

• $1 \leq N \leq 2 \ 000$
• $1 \leq K \leq N$
• $1 \leq$ diametrele discurilor $\leq N$

Exemplul 1

hanoi.in

3 2
2 1 3

hanoi.out

6

Explicație

Cele $6$ moduri distincte de așezare sunt:

Vezi Figura 2.

Exemplul 2

hanoi.in

4 3
4 1 1 3

hanoi.out

15

Explicație

Cele $15$ moduri distincte de așezare sunt: