calatorie

Time limit: 0.03s Memory limit: 128MB Input: calatorie.in Output: calatorie.out

Dorești să mergi în vacanță și ai hotărât deja destinația. Formal, te afli în punctul (0,0)(0, 0) al unui sistem cartezian de axe și trebuie să ajungi în punctul de coordonate (X,X)(X, X). Țara în care te afli are drumuri paralele cu axele de coordonate la fiecare abscisă și la fiecare ordonată număr natural. În fiecare moment, dacă eşti în punctul de coordonate (a,b)(a, b), ai 22 variante de deplasare: în punctul (a,b+1)(a, b+1) sau în punctul (a+1,b)(a+1, b). La fiecare astfel de pas consumi un litru de carburant. Prin unele puncte de forma (a,a)(a, a) nu poți trece, iar în celelalte puncte care au abscisa egală cu ordonata poți trece și în plus, acolo se află câte o stație de benzină unde poți să “faci plinul”. Prin toate punctele care nu au abscisa egală cu ordonata poți trece dar acolo nu se află stații de benzină. Rezervorul mașinii tale are o capacitate de KK litri.

Cerință

Determinați toate traseele distincte prin care poți ajunge la destinație. Două trasee sunt distincte dacă diferă prin cel puţin un punct.

Date de intrare

Fișierul calatorie.in conține pe prima linie două numere separate printr-un spațiu, XX și KK, cu semnificația din enunț. Pe linia a 22-a se găsește un număr NN, care reprezintă numărul de puncte de forma (a,a)(a, a) care nu pot fi traversate. Pe fiecare dintre următoarele NN linii se află câte un număr aa, cu semnificația că punctul (a,a)(a, a) nu poate fi vizitat.

Date de ieșire

Fișierul calatorie.out conține pe prima linie un singur număr natural reprezentând valoarea cerută, modulo 997997.

Restricții și precizări

  • 1X50 0001 \leq X \leq 50 \ 000;
  • 2K502 \leq K \leq 50;
  • 0N100 \leq N \leq 10;
  • Călătoria începe cu rezervorul plin;
  • Se garantează că există cel puțin un drum;

Exemplu

calatorie.in

3 10
1
1

calatorie.out

8

Log in or sign up to be able to send submissions!