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

Drumul Scufitei Rosie spre bunicuta trece prin Padurea Fermecata, padure care este traversata de un rau. Peste acest rau exista un singur pod alcatuit din $N$ scanduri. In timpul traversarii podului Scufita Rosie poate face pasi de lungime $1$ sau $K$. Din pacate podul are $M$ scanduri lipsa (ale caror numere de ordine Scufita Rosie le cunoaste), pe care nu se poate pasi. Fiind o adepta a diversitatii Scufita Rosie vrea ca in fiecare zi cand isi viziteaza bunicuta configuratia pasilor ei sa fie alta, asa ca va roaga pe voi sa aflati in cate moduri se poate traversa podul. Fiind totusi constienta ca acesta poate fi un numar extrem de mare ii este de ajuns sa stie restul impartirii lui la **9901**

Drumul Scufitei Rosie spre bunicuta trece prin Padurea Fermecata, padure care este traversata de un rau. Peste acest rau exista un singur pod alcatuit din $N$ scanduri. In timpul traversarii podului Scufita Rosie poate face pasi de lungime $1$ sau $K$. Din pacate podul are $M$ scanduri lipsa (ale caror numere de ordine Scufita Rosie le cunoaste), pe care nu se poate pasi. Fiind o adepta a diversitatii Scufita Rosie vrea ca in fiecare zi cand isi viziteaza bunicuta configuratia pasilor ei sa fie alta, asa ca va roaga pe voi sa aflati in cate moduri se poate ajunge la scandura $N$. Fiind totusi constienta ca acesta poate fi un numar extrem de mare ii este de ajuns sa stie **restul impartirii lui la 9901**.

h2. Date de intrare

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

Fişierul de intrare $pod.in$ va contine pe prima linie 3 numere, $N$, $M$ si $K$, avand semnificatia din enunt. Pe a 2-a linie se vor afla $M$ numere naturale, reprezentand pozitiile scandurilor lipsa.

h2. Date de ieşire

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

În fişierul de ieşire $pod.out$ se va afisa un singur numar natural, restul numarului de posibilitati la 9901.

h2. Restricţii

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

* $1 ≤ N ≤ 1.000.000.000$
* $0 ≤ M ≤ 1.000$
* $1 ≤ K ≤ 20$
* Pentru $15$% din teste $N ≤ 1.000.000$
* Pentru alte $15$% din teste $M = 0$

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

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

| 10 3 2
  1 4 6
| 3

|

h3. Explicaţie
 
...
 

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

4949