Simulation - Lot 2014 Baraj 2 Juniori | robot

Studenţii Facultăţii de Informatică din cadrul Universităţii din Cluj, au conceput roboţi care şterg praful, plantează copaci, pun gresie, servesc masa, etc. Botezat „Rosie“, robotul care şterge praful are două braţe ($\textcolor{red}S$ — stâng şi $\textcolor{red}D$ — drept) pe care sunt montate nişte perii ce sunt învârtite cu ajutorul unui motoraş. Braţul robotului este programat să se poziţioneze în dreptul unei suprafeţe, periile învârtite de motoraş parcurg suprafaţa ştergând în acest fel praful de pe ea.

Pentru o demonstraţie, robotul este aşezat în faţa unei etajere cu $N$ rafturi numerotate în ordine, de jos în sus, cu numere de la $1$ la $N$. Braţul stâng ($\textcolor{red}S$) al robotului este poziţionat în dreptul primului raft iar celălalt braţ ($\textcolor{red}D$) în dreptul celui de-al $K$-lea raft.

Pentru ştergerea prafului, deplasarea braţelor robotului este programată astfel:

• fiecare braţ se deplasează doar de jos în sus, de la raftul în dreptul căruia este poziţionat la un moment dat, la raftul situat imediat deasupra acestuia;
• din minut în minut, se deplasează doar unul din braţe, se poziţionează în dreptul raftului corespunzător şi şterge praful de pe acesta;
• dacă ambele braţe ajung în dreptul aceluiaşi raft, atunci robotul se blochează şi demonstraţia se încheie fără succes.

Cerinţă

Ştiind că demonstraţia se termină în momentul în care braţul drept ($\textcolor{red}D$) al robotului a ajuns pe ultimul raft al etajerei, scrieţi un program care calculează numărul $M$ de modalităţi diferite în care poate fi programat robotul pentru a asigura succesul demonstraţiei. Programul va afişa restul împărţirii numărului $M$ la $64 \ 997$.

Date de intrare

Fişierul de intrare robot.in conţine pe prima linie două numere naturale $N$ şi $K$, în această ordine, separate printr-un spaţiu, având semnificaţia din enunţ.

Date de ieșire

În fişierul de ieșire robot.out se va scrie pe prima linie un singur număr natural ce reprezintă restul împărţirii numărului $M$ la $64 \ 997$.

Restricții și precizări

• $2 \leq K \leq N \leq 2 \ 800$
• cele două braţe NU se pot mişca simultan;
• un braţ poate fi programat să se deplaseze în dreptul unui raft de pe care a fost deja şters praful;
• un mod de programare al robotului este definit printr-o succesiune de deplasări ale braţelor $\textcolor{red}S$ și $\textcolor{red}D$;
• două moduri de programare ale robotului sunt diferite dacă acestea au cel puţin o deplasare $\textcolor{red}S$ sau $\textcolor{red}D$ diferită.

Exemplu

robot.in

5 2 

robot.out

5

Explicație

Cu $\textcolor{red}X: Y \rightarrow Z$ am notat deplasarea brațului $\textcolor{red}X$ de la raftul $Y$ la raftul $Z$.
Sunt $5$ modalităţi de programare a robotului pentru ca braţul drept să ajungă la ultimul raft:

1. $\textcolor{red}D: 2 \rightarrow 3$, $\ \textcolor{red}D: 3 \rightarrow 4$, $\ \textcolor{red}D: 4 \rightarrow 5$;
2. $\textcolor{red}D: 2 \rightarrow 3$, $\ \textcolor{red}S: 1 \rightarrow 2$, $\ \textcolor{red}D: 3 \rightarrow 4$, $\ \textcolor{red}D: 4 \rightarrow 5$;
3. $\textcolor{red}D: 2 \rightarrow 3$, $\ \textcolor{red}S: 1 \rightarrow 2$, $\ \textcolor{red}D: 3 \rightarrow 4$, $\ \textcolor{red}S: 2 \rightarrow 3$, $\ \textcolor{red}D: 4 \rightarrow 5$;
4. $\textcolor{red}D: 2 \rightarrow 3$, $\ \textcolor{red}D: 3 \rightarrow 4$, $\ \textcolor{red}S: 1 \rightarrow 2$, $\ \textcolor{red}D: 4 \rightarrow 5$;
5. $\textcolor{red}D: 2 \rightarrow 3$, $\ \textcolor{red}D: 3 \rightarrow 4$, $\ \textcolor{red}S: 1 \rightarrow 2$, $\ \textcolor{red}S: 2 \rightarrow 3$, $\ \textcolor{red}D: 4 \rightarrow 5$.