Fişierul intrare/ieşire:	2sah.in, 2sah.out	Sursă	OJI 2015, clasele 11-12
Autor	Adrian Panaete	Adăugată de	FMI Suditu Thomas •Thomas
Timp execuţie pe test	0.05 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

2sah

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 coloana 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 cere doar restul modulo 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 (trebuie afişat restul 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 (trebuie afişat restul modulo 100003).

Restricţii

• 1 ≤ k ≤ n ≤ 1 000 000 000 (un miliard)
• La cerinţa 1 pentru 80% dintre teste k ≤ n ≤ 1 000 000, iar pentru alte 20% din teste k ≤ n ≤ 1 000 000 000
• La cerinţa 2 pentru 30% dintre teste k ≤ n ≤ 1000, pentru alte 30% dintre teste k ≤ n ≤ 1 000 000, iar pentru restul de 40% dintre teste k ≤ n ≤ 1 000 000 000.
• Rezolvarea corectă a primei cerinţe asigură 30% din punctajul testului respectiv.
• Rezolvarea corectă a celei de a doua cerinţe asigura 70% din punctajul testului respectiv.

Exemplu

Explicaţie

În primul exemplu 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ţ)

În al doilea exemplu 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.

Cum se trimit solutii?