Fişierul intrare/ieşire:produse.in, produse.outSursăAlgoritmiada 2016 Runda 1 Seniori
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Produse

Dându-se un şir de N numere naturale, câte submulţimi de indici ai şirului au proprietatea că produsul elementelor aflate la indicii respectivi este mai mic sau egal cu D?

În calcularea răspunsului nu se va considera mulţimea vidă.

Date de intrare

Fişierul de intrare produse.in va conţine pe prima sa linie valorile N şi D. Următoarea linie va conţine N numere naturale, reprezentând valorile din şir.

Date de ieşire

În fişierul de ieşire produse.out se va afla o singură linie care va conţine răspunsul problemei modulo 109 + 7.

Restricţii

  • 1 ≤ N, D ≤ 200.000
  • Fiecare număr din şir va fi mai mic sau egal cu D şi mai mare sau egal cu 1.
  • Pentru teste in valoare de 15 puncte N ≤ 20
  • Pentru alte teste in valoare de 30 de puncte cele N numere sunt generate aleator uniform din intervalul [1, D]

Exemplu

produse.inproduse.out
6 50
2 2 2 3 4 10
39
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?