D - Crackul mijlociu

Time limit: 1s Memory limit: 64MB Input: Output:

Cerință

Un număr perfect este un număr a cărui sumă a divizorilor mai mici ca el este fix numărul în sine.

Se dă un șir cu NN numere, câte subșiruri au produsul un număr perfect mai mic sau egal cu un XX dat?

Date de intrare

Pe prima linie se găsesc două numere întregi, NN și XX.
Pe a doua linie se află șirul de NN numere.

Date de ieșire

Răspunsul modulo 109+710^9+7.

Restricții și precizări

  • 1N1051 \leq N \leq 10^5
  • 1X,vi1091 \leq X, v_i \leq 10^9

Exemplu

stdin

6 15
1 3 3 2 6 28

stdout

6

Explicație

Subșirul care conține numărul 2828 nu este numărat pentru că este mai mare ca XX chiar daca este număr perfect (28=1+2+4+7+1428=1+2+4+7+14).
Toate subșirurile de produs 66 sunt considerate bune deoarece 66 este un număr perfect (6=1+2+36=1+2+3).

Log in or sign up to be able to send submissions!