Given a sequence \(a_1{\dots}a_n\). It's guaranteed that \(a_i|m\) for all i, means every element in the sequence divides \(m\).

A graph is built with this sequence. Specifically, an edge \((u,v)\) exists when and only when \(u and \(a_u|a_v\). Obviously, this is a DAG.

Your task is to calculate the count of different paths from 1 to i for all i between 1 and n.

Input

The first line contains two integers, \(n\) and \(m\).

The second line contains \(n\) integers, representing the sequence \(a_1{\dots}a_n\).

It's guaranteed that \(a_1=1\).

Output

\(n\) lines. Each line contains an integer, the \(i_{th}\) integer is the count of different paths from 1 to i modulo \(10^9+7\).

Constraints

\(1\le n\le 2 \times 10^5\)

\(1\le m\le 10^{19}\)