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<v$ 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}$