Count of paths

2

2 votes
Algorithms, Hard, Square Root Decomposition
Problem

Given a sequence a1an. 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 a1an.

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

1n2×105

1m1019

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The two paths from 1 to 3 are 13 and 123.

Editor Image

?