All Tracks Algorithms Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

April Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?