$A(2) = 3$.
$A(i) = x * A(i - 1) + y * A(i - 2)$, pentru orice $i$ mai mare sau egal cu 3.

Se da o lista de pozitii $P1, P2.. Pk$, cu semnificatia ca valorile $A(P1), A(P2), ... A(Pk)$ sunt *cunoscute*. Se considera ca valorile $A(1)$ si $A(2)$ sunt de-asemenea cunoscute, chiar daca numerele 1 si 2 s-ar putea sa nu fie incluse in lista $P$.
 
Procedura de calcul pentru un anumit termen al sirului, fie el $A(n)$ este urmatoarea:
 
1. Daca $A(n)$ este *cunoscut*, finalizam procedura.
2. Daca $A(n - 1)$ nu este *cunoscut*, vom aplica procedura de calcul pentru $A(n - 1)$.
3. Daca $A(n - 2)$ nu este *cunoscut*, vom aplica procedura de calcul pentru $A(n - 2)$.
4. Aplicam relatia sirului: $A(n) = x * A(i - 1) + y * A(i - 2)$.
 
Cate proceduri de calcul vor fi realizate pentru a calcula valoarea lui $A(n)$?
Deoarece acest numar poate fi foarte mare, rezultatul se va afisa *modulo 9007*.
 

h2. Date de intrare

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

Fişierul de intrare $ccount.in$ va contine pe prima sa linie numarul $N$ si numarul $K$, reprezentand indicele termenului pentru care oferim raspunsul, respectiv numarul de elemente al listei $P$.
Cea de a doua linie va contine $K$ numere, reprezentand lista $P$.

h2. Date de ieşire

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

În fişierul de ieşire $ccount.out$ se va afla raspunsul problemei *modulo 9007*.

h2. Restricţii

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

* $1≤ N ≤ 10^5%$
* $A$ *modulo* $B$ se refera la restul impartirii numarului A la numarul B.
Urmatoarele relatii sunt valabile si pot fi necesare pentru a calcula rezultatul fara a depasi tipurile de date C++:
 
$(A + B) modulo C = (A modulo C + B modulo C) modulo C$
$(A * B) modulo C = ((A modulo C) * (B modulo C)) modulo C$

h2. Exemplu