drum3

Drum3

== include(page="template/taskheader" task_id="drum3") ==

Poveste şi cerinţă...

Tamara are o tabla patratica cu $N$ coloane si $N$ linii, si un pion in coltul stanga sus al tablei care poate fi deplasat doar la dreapta sau in jos. Tamara se intreaba prin cate drumuri posibile poate duce pionul in coltul dreapta jos al tablei facand exact $K$ schimbari de directie? O schimbare de directie reprezinta schimbarea directiei miscarii pionului din jos in dreapta sau din dreapta in jos. Initial pionul se poate deplasa in orice directie (jos sau dreapta).
 
Exemplu:
 
  1 2 3 4 5 6 7 8
1 {**x x S**} o o o o o
2 o o {**x**} o o o o o
3 o o {**x**} o o o o o
4 o o {**S x x S**} o o
5 o o o o o {**x**} o o
6 o o o o o {**x**} o o
7 o o o o o {**S x S**}
8 o o o o o o o {**x**}
 
Un drum cu $5$ schimbari de directie intr-o tabla de $8x8$.
Schimbarile de directie sunt marcate cu $**S**$.

h2. Date de intrare

Fişierul de intrare $drum3.in$ ...

Fisierul de intrare $drum3.in$ va contine pe prima linie numerele $N$ si $K$ reprezentand dimensiunea tablei si respectiv numarul de schimbari de directie.

h2. Date de ieşire

În fişierul de ieşire $drum3.out$ ...

In fisierul de iesire $drum3.out$ veti afisa un singur numar $R$, reprezentand numarul de drumuri posibile ale pionului **modulo 30013**.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $3 ≤ N ≤ 5 000$
* $1 ≤ K < 2 * (N-1)$

h2. Exemplu
table(example). |_. drum3.in |_. drum3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

| 4 2 | 4 |
| 4 3 | 8 |
| 5 3 | 18 |

== include(page="template/taskfooter" task_id="drum3") ==

4536