== include(page="template/taskheader" task_id="progresii3") ==
Gigel este indragostit de progresii aritmetice. Toata ziua sta si se gandeste la ele asa ca atunci cand a vazut problema 'Progresii 2':problema/progresii2 nu putea fi mai fericit. Putea sa stie exact cate progresii aritmetice poate forma de o anumite lungime $N$ cu numerele de la $1$ la $V$. La scurt timp insa si-a dat seama ca solutia acelei probleme nu ii este utila deloc deoarece el are $K$ numere pe care nu le place, deci ar vrea sa nu le vada in nicio progresie aritmetica. *Aceste $K$ numere sunt destul de apropiate, distanta cea mai mare dintre ele fiind de maxim $50.000$*.
Date fiind $V$, $N$ si cele $K$ numere trebuie sa-i spuneti lui Gigel cate progresii aritmetice cu *ratia pozitiva* de marime $N$ se pot forma cu numerele de la $1$ la $V$ mai putin cele $K$ date. In schimb el va va oferi $100$ de puncte.
Deoarece numarul acesta poate fi cam mare Gigel vrea doar restul impartii acestui numar la $1.000.000.009$ $(un miliard noua)$
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $progresii3.in$ va contine pe prima linie 3 numere naturale $V$, $N$ si $K$. Urmatorul rand va contine $K$ numere naturale $A{~1~}$, $A{~2~}$, ..., $A{~K~}$ reprezentand cele $K$ numere pe care Gigel nu le place.
Fişierul de intrare $progresii3.in$ ...
h2. Date de ieşire
În fişierul de ieşire $progresii3.out$ trebuie sa se gaseasca un singur numar natural, numarul de progresii aritmetice de marime $N$ care contin numere de la $1$ la $V$ mai putin cele $K$ date in fisierul de intrare.
În fişierul de ieşire $progresii3.out$ ...
h2. Restricţii
* $2 ≤ V ≤ 1.000.000.000.000 (10^12^)$
* $2 ≤ N ≤ 5000$
* $1 ≤ K ≤ 50$
* $K,N ≤ V$
* $Pentru 20 de puncte V ≤ 100.000, N ≤ 50, K ≤ 30 si distanta maxima dintre doua din cele K valori este maxim 500$
* $Pentru inca 20 de puncte V ≤ 10.000.000, 100 ≤ N ≤ 150, K ≤ 30 si distanta maxima dintre doua din cele K valori este maxim 500$
* $Pentru inca 20 de puncte N, K ≤ 20 si distanta maxima dintre doua din cele K valori este maxim 500$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. progresii3.in |_. progresii3.out |
| 5 2 1
3
| 6
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 100 10 4
16 25 49 64
| 308
|
h3. Explicaţie
Pentru primul exemplu cele 6 progresii aritmetice de 2 elemente formate din valorile ${1, 2, 4, 5}$ sunt $(1,2)$, $(1,4)$, $(1,5)$, $(2,4)$, $(2,5)$, $(4,5)$
...
== include(page="template/taskfooter" task_id="progresii3") ==
