Șir

Corneluș a învățat să numere. El pornește întotdeauna de la $1$, numără din $1$ în $1$, nu greșește niciodată numărul următor, însă ezită uneori și atunci spune numărul curent de mai multe ori. Sora lui, Corina, îl urmărește și face tot felul de calcule asupra modurilor în care numără fratele ei. Astfel, ea urmărește până la cât numără $(U)$, câte numere spune în total $(N)$ și, pentru a aprecia cât de ezitant este, numărul maxim de repetări $(R)$ ale unei valori. De exemplu, el poate număra până la $8$ astfel: $1 \ 2 \ 3 \ 3 \ 4 \ 5 \ 6 \ 7 \ 7 \ 7 \ 7 \ 8 \ 8$. În acest caz, numără până la $8 \ (U=8)$, spune $13$ numere $(N=13)$ și ezită cel mai mult la $7$, spunându-l de $4$ ori $(R=4)$.

Cerințe

1. Cunoscând numărul total de numere $N$ și ultimul număr spus $U$, trebuie să calculați câte șiruri diferite au exact $N$ numere și se termină cu numărul $U$.
2. Cunoscând numărul total de numere $N$ și numărul maxim de repetări $R$ ale unei valori, trebuie să calculați câte șiruri diferite au exact $N$ numere și fiecare valoare se repetă de cel mult $R$ ori.

Deoarece numărul de șiruri poate fi foarte mare, calculați restul împărțirii acestui număr la $20 \ 173 \ 333$.

Date de intrare

Din fișierul sir.in se citesc trei numere naturale, $P, N$ și $X$, scrise în această ordine, cu câte un spațiu între ele. $P$ poate avea una dintre valorile $1$ sau $2$, iar $N$ este numărul de numere din șir. Când $P$ are valoarea $1$, numărul $X$ reprezintă ultimul număr spus $(U)$, iar când $P$ are valoarea $2$, $X$ reprezintă numărul maxim de repetări ale unei valori $(R)$.

Date de ieșire

În fișierul sir.out se scrie o singură valoare, astfel:

• dacă $P$ a avut valoarea $1$, valoarea reprezintă numărul de șiruri distincte care au exact $N$ numere și se termină cu numărul $X$
• dacă $P$ a avut valoarea $2$, valoarea reprezintă numărul de șiruri distincte care au exact $N$ numere și fiecare număr se repetă de cel mult $X$ ori.

În ambele cazuri, deoarece numărul rezultat poate fi foarte mare, se va scrie restul împărțirii acestui număr la $20 \ 173 \ 333$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $X \leq N$
• Ultima valoare spusă poate să apară de mai multe ori;
• Testele cu $P=1$ vor totaliza $50\%$ din punctaj, restul de $50\%$ din punctaj fiind pentru $P=2$;
• Pentru teste cumulând 50 de puncte valoarea lui $N$ nu depășește $1\ 000$.

Exemplul 1

sir.in

1 5 3

sir.out

6

Explicație

Se rezolvă cerința $1$. Pentru $N=5$, $X=3$, sunt $6$ șiruri care au exact $N$ numere și se termină cu $3$: $[1 \ 1 \ 1 \ 2 \ 3]$, $[1 \ 1 \ 2 \ 2 \ 3]$, $[1 \ 1 \ 2 \ 3 \ 3]$, $[1 \ 2 \ 2 \ 2 \ 3]$, $[1 \ 2 \ 2 \ 3 \ 3]$ și $[1 \ 2 \ 3 \ 3 \ 3]$.

Exemplul 2

sir.in

2 5 2

sir.out

8

Explicație

Se rezolvă cerința $2$. Pentru $N=5$, $X=2$, sunt $8$ șiruri care au exact $N$ numere și fiecare număr se repetă de cel mult $2$ ori $[1 \ 1 \ 2 \ 2 \ 3]$, $[1 \ 1 \ 2 \ 3 \ 3]$, $[1 \ 1 \ 2 \ 3 \ 4]$, $[1 \ 2 \ 2 \ 3 \ 3]$, $[1 \ 2 \ 2 \ 3 \ 4]$, $[1 \ 2 \ 3 \ 3 \ 4]$, $[1 \ 2 \ 3 \ 4 \ 4]$, $[1 \ 2 \ 3 \ 4 \ 5]$.

Exemplul 3

sir.in

2 10 3

sir.out

274

Explicație

Se rezolvă cerința $2$. Pentru $N=10$, $X=3$, sunt $274$ de șiruri care au exact $10$ numere și fiecare număr se repetă de cel mult $3$ ori.