Produtos na roda

Time limit: 3000 msMemory limit: 256 MB

Há $n$ posições numeradas em uma roda. Queremos colocar um inteiro $x_i$ entre $1$ e $M$ em cada posição. Para cada par de posições consecutivas, um sensor informa o produto dos dois números.

Dados $b_1,\ldots,b_n$ , conte as sequências $(x_1,\ldots,x_n)$ que satisfazem para todo , considerando .

As posições são identificadas: rotações de uma sequência podem ser sequências diferentes. Para $n=1$ , a única condição é $x_1^2=b_1$ .

Input

A primeira linha contém $n$ e $M$ ( $1 \le n \le 200\,000$ ; $1 \le M \le 10^{12}$ ). A segunda contém inteiros ().

Output

Imprima o número de sequências possíveis, sem tomar módulo.

Samples

Sample 1

Input

4 6
6 12 12 6

Output

As sequências são (1,6,2,6), (2,3,4,3) e (3,2,6,2).

Sample 2

Input

3 5
6 15 10

Output

A única sequência é (2,3,5).

Sample 3

Input

2 10
6 8

Output

Os dois sensores medem o mesmo produto, mas informam valores diferentes.