Given a sequence a1…an. It's guaranteed that ai|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 au|av. 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 a1…an.
It's guaranteed that a1=1.
Output
n lines. Each line contains an integer, the ith integer is the count of different paths from 1 to i modulo 109+7.
Constraints
1≤n≤2×105
1≤m≤1019
The two paths from 1 to 3 are 1−3 and 1−2−3.