factoria

Cerință

Trraian, de ziua lui, a plecat într-o excursie. El a ajuns în țara Factoria, unde a primit de la vrăjitorul Factorios un cadou. Acel cadou conținea un șir $a$ de $n$ numere $a_1, a_2, .., a_n$ și un număr $k$. Pentru ca Factorios să nu îi ia șirul lui Trraian, el i-a pus următoarea întrebare: "Câte subsecvențe ale șirului $a$ primit de tine au proprietatea că produsul numerelor din secvență este divizibil cu factorialul lui $k$?". Trraian își dorește foarte mult să păstreze șirul, dar acesta nu știe să răspundă la întrebarea lui Factorios, așa că vă roagă pe voi să îl ajutați să răspundă la întrebare și vă va fi foarte recunoscător.

Definiții: O subsecvență a unui șir $a$ este un șir de numere care apar pe poziții consecutive în $a$. Factorialul unui număr $k$ este egal cu $1 \cdot 2 \cdot 3 \cdot .. \cdot k$ și se notează $k!$.

Date de intrare

Pe prima linie a fișierului de intrare factoria.in se vor afla două numere naturale, $n$ și $k$. Pe a doua linie se vor afla cele $n$ numere naturale, $a_1, a_2, \dots, a_n$.

Date de ieșire

Pe prima linie a fișierului de ieșire factoria.out se va găsi un singur număr întreg, răspunsul la întrebarea lui Factorios.

Restricții și precizări

• $1 \leq n \leq 200 \ 000$
• $1 \leq k \leq 10^6$
• $1 \leq a_i \leq 10^6$, pentru $i$ de la $1$ la $n$.

Exemplu

factoria.in

6 4
3 8 24 48 5 7

factoria.out

16

Explicație

Cele $16$ secvențe sunt: $[3, 8]$, $[3, 8, 24]$, $[3, 8, 24, 48]$, $[3, 8, 24, 48, 5]$, $[3, 8, 24, 48, 5, 7]$, $[8, 24]$, $[8, 24, 48]$, $[8, 24, 48, 5]$, $[8, 24, 48, 5, 7]$, $[24]$, $[24, 48]$, $[24, 48, 5]$, $[24, 48, 5, 7]$, $[48]$, $[48, 5]$, $[48, 5, 7]$