Count of paths
Tag(s):

## Algorithms, Algorithms, Hard, Square Root Decomposition

Problem
Editorial
Analytics

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

SAMPLE INPUT
4 6
1 3 6 2
SAMPLE OUTPUT
1
1
2
1
Explanation

The two paths from 1 to 3 are $1-3$ and $1-2-3$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

April Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Basic Programming > Implementation
• Math > Combinatorics
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures

?