Se dă o tablă de şah cu n+1 linii (numerotate de sus în jos începând cu 1) şi 2n+1 coloane (numerotate de la stânga la dreapta începând cu 1). Pe prima linie pătratul din mijloc conţine 1 gram de fân, iar celelalte pătrate de pe prima linie nu conţin nimic. Începând cu linia a doua fiecare pătrat conţine o cantitate de fân obţinută prin adunarea cantităţilor de fân din cele 3 pătrate ale liniei anterioare cu care se învecinează (pe verticală şi diagonală). De exemplu dacă n=3 tabla are 4 linii, 7 coloane şi următoarea configuraţie.
Un cal pleacă de pe prima linie, de pe o coloană k≤n, sare din orice poziţie (i,j) în poziţia (i+1,j+2) atât timp cât este posibil şi mănâncă tot fânul din pătratele prin care trece. De exemplu, pentru n=3 şi k=2, pătratele prin care trece calul sunt marcate cu asterisc ( * )
Cerinţă
1. Cunoscând n şi k, să se calculeze cantitatea de fân de pe linia k a tablei.
2. Cunoscând n şi k, să se calculeze câte grame de fân mănâncă un cal care pleacă de pe prima linie, de pe coloana k.
Întrucât aceste numere pot fi mari, se cer doar resturile împărţirii la 100003 ale acestor numere.
Date de intrare
Fişierul de intrare 2sah.in va conţine pe prima linie un număr t cu valoarea 1 sau 2. Pe a doua linie a fişierului de intrare se găsesc două numere naturale n şi k separate printr-un spaţiu.
Dacă t=1 se va rezolva prima cerinţă, deci pentru valoarea n citită tabla are n+1 linii şi 2n+1 coloane, iar k reprezintă numărul liniei de pe care trebuie calculată cantitatea de fân.
Dacă t=2 se va rezolva a doua cerinţă, deci pentru valoarea n citită tabla are n+1 linii şi 2n+1 coloane, iar k reprezintă numărul coloanei din prima linie de unde pleacă calul.
Date de ieşire
Dacă t din fişierul de intrare este 1 se va rezolva doar prima cerinţă.
În acest caz fişierul de ieşire 2sah.out va conţine un singur număr reprezentând cantitatea totală de fân din toate pătratele situate pe tabla pe linia k (rezultatul trebuie afişat modulo 100003).
Dacă t din fişierul de intrare este 2 se va rezolva doar a doua cerinţă.
În acest caz fişierul de ieşire 2sah.out va conţine un singur număr reprezentând cantitatea totală de fân mâncată de un cal care pleacă de pe linia 1 şi coloana k (rezultatul trebuie afişat modulo 100003).
Restricţii
• 1 ≤ k ≤ n ≤ 1000000000 (un miliard)
Exemple
2sah.in
2sah.out
Explicaţii
1
3 2
3
t=1, deci se rezolvă prima cerinţă.
Pe linia a doua există 3 pătrate care conţin fiecare câte un gram de fân.(vezi desenul din enunţ)
2
3 2
2
t=2, deci se rezolvă doar a doua cerinţă.
Traseul calului este: (1,2) -> (2,4) -> (3,6) adică exact pătrăţelele marcate cu asterisc în desenul din enunţ. Prima poziţie nu conţine fân, iar celelalte două conţin câte un gram de fân. Deci calul mănâncă 2 grame de fân.
