Update appNew update is available. Click here to update.

Count of paths

Last Updated: 7 Jul, 2021
Difficulty: Hard


Try Problem

Given a sequence of N integers: arr0, arr1, arr2, ….. arrN-1 and an integer K

K is divisible by all the array elements, ie: K % arri = 0 for (0 <= i <= N-1).

A directed graph is built using this sequence. A directed edge from the jth to the ith array element exists if j < i and ai is divisible by aj, ie: ai % aj = 0.

Find the count of different paths from 0th element to ith element for 0 <= i <= N-1. As the answer can be very large, return answer modulo 109+7.


Input Format:
The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow. 

The first line contains two integers, 'N' and 'K', where N represents the sequence length.

The next line contains N integers, 'ai' for (0 <= i <= N-1).
Output Format:
Print N integers, where ith element denotes the count of different paths from 1st element to ith element.

Output for each test case will be printed in a separate line,
You are not required to print anything; it has already been taken care of. Just implement the function.
1 <= T <= 10
1 <= N <= 5 * 10^4    
1 <= K <= 10^9  
1 <= ai <= 10^5

Time limit: 1 sec