piruete

Piruete

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

Poveste şi cerinţă...

Fie un număr natural $N$ şi o încăpere de lungime $2*N+2$ văzută ca un interval închis $[-N-1,N+1]$. În centrul $C$ al camerei $(C = 0)$, se află iniţial o balerină pe nume Costelina Salopeta. Ea urmează să efectueze $T$ paşi de dans de lungime $1$, făcând primul pas spre dreapta. În cele $2*N$ puncte distincte de coordonate întregi din interiorul camerei se pot plasa $K$ obstacole. Atunci când balerina ajunge într-un punct cu obstacol, ea se împiedică şi face o piruetă. Astfel ea îşi schimbă sensul de mişcare, iar obstacolul din punctul respectiv dispare.
 
p=. !problema/piruete?balerina.jpg!
 
Nu se pot pune obstacole în punctele de coordonate $-N-1, 0$ respectiv $N+1$. Pereţii camerei de coordonate $-N-1$ respectiv $N+1$ se consideră obstacole permanente ce nu vor dispărea la atingere, iar punctul de coordonată $C=0$ reprezintă poziţia iniţială a Costelinei.
 
Dându-se valorile lui $T, N$ şi $K$, calculaţi în câte moduri se pot plasa cele $K$ obstacole, astfel încât după o reprezentaţie completă de $T$ paşi Costelina să se întoarcă în punctul de pornire $C$.

h2. Date de intrare

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

Fişierul $piruete.in$ conţine pe prima linie numerele naturale $T, N$ şi $K$ separate prin câte un spaţiu, cu semnificaţiile de mai sus.

h2. Date de ieşire

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

Fişierul $piruete.out$ va conţine pe prima linie un singur număr natural reprezentând răspunsul $modulo 10^9^ + 7$.

h2. Restricţii

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

* $0 ≤ T ≤ 200, T$ este număr par
* $1 ≤ N ≤ 100$
* $0 ≤ K ≤ 2*N$
* Atentie! Răspunsul se cere modulo $10^9^ + 7$
* Pentru $10%$ din teste avem $N ≤ 10$
* Pentru $30%$ din teste avem $N ≤ 30$
* Pentru $70%$ din teste avem $T ≤ 2*N+2$

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|6 3 4
|7
|
|8 3 1
|3
|

h3. Explicaţie

...

 
Balerina va efectua $T=6$ paşi într-o cameră de lungime $2*N+2=2*3+2=8$, se plasează $K=4$ obstacole.
Există $7$ modalităţi de amplasare a obstacolelor:
$1. [.x.Cxxx]  2. [.xxC.xx]  3. [x.xC.xx]$
$4. [xx.Cx.x]  5. [xx.Cxx.]  6. [xxxC.x.]$
$7. [xxxC..x]$
S-a notat cu ’.’ poziţia unui loc liber, respectiv cu ’x’ poziţia unui obstacol.
 

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