Fișierul intrare/ieșire	trepte.in, trepte.out	Sursă	ad-hoc
Autor		Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.6 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Trepte

Pentru a scăpa de rușinea adusă de rezultatele lui în comparație cu Semicerc, Costel s-a apucat (pe lângă multe altele!) să facă Fitness^TM. Deoarece e închis la sală, el s-a adaptat la situație și a început să facă Fitness^TM pe scara din casa lui. Scara din casa lui Costel este formată din N + 1 trepte (numerotate de la 0 la N). El începe de pe treapta cu numărul 0 și poate urca câte 1 sau 2 trepte la fiecare pas. Din păcate, M dintre trepte sunt mai șubrede, iar Costel nu poate păși pe ele.

Pentru a scăpa de rușine, Costel se întreabă care este numărul de moduri de a ajunge pe treapta cu numărul N, modulo 10⁹+7.

Date de intrare

Fișierul de intrare trepte.in conține pe prima linie numerele N și M, care reprezintă numărul de trepte ale scării, respectiv numărul de trepte șubrede. Linia i + 1 conține numărul a_i, cu semnificația că treapta a_i este șubredă.

Date de ieșire

În fișierul de ieșire trepte.out conține pe prima linie răspunsul căutat, modulo 10⁹+7.

Restricții și precizări

• 1 ≤ a_i < a_{i + 1} < N pentru oricare 1 ≤ i < M.
• 0 ≤ M < N.
• Pentru 10 puncte, M = 0 și 1 ≤ N ≤ 10⁵;
• Pentru alte 60 de puncte, 0 ≤ M < N ≤ 10⁵;
• Pentru alte 20 de puncte, a₁ ≤ 10⁶, N – a_M ≤ 10⁶, a_i – a_i-1 ≤ 10⁶ pentru oricare 1 < i ≤ M și 1 ≤ < ≤ 10⁶, 1 ≤ N ≤ 10¹²;
• Pentru restul punctelor, M = 0 și 1 ≤ N ≤ 10¹⁸.

Exemplu

Explicație

Cele 4 moduri de a urca scările sunt:

• 0 → 1 → 2 → 4 → 5 → 6
• 0 → 1 → 2 → 4 → 6
• 0 → 2 → 4 → 5 → 6
• 0 → 2 → 4 → 6