Fişierul intrare/ieşire:	progresii3.in, progresii3.out	Sursă	Infoarena Cup 2014
Autor	Adrian Budau	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.45 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Progresii 3

Gigel este indragostit de progresii aritmetice. Toata ziua sta si se gandeste la ele asa ca atunci cand a vazut problema Progresii 2 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)

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₁, A₂, ..., A_K reprezentand cele K numere pe care Gigel nu le place.

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.

Restricţii

• 2 ≤ V ≤ 1.000.000.000.000 (10¹²)
• 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

Exemplu

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)

Cum se trimit solutii?