0

# Count of paths

Difficulty: HARD
Contributed By
Anshul Garg
Avg. time to solve
50 min
Success Rate
60%

Problem Statement

#### 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,
``````
##### Note:
``````You are not required to print anything; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 5 * 10^4
1 <= K <= 10^9
1 <= ai <= 10^5

Time limit: 1 sec
``````
##### Sample Input 1:
``````2
6 60
1 2 3 4 5 6
1 10
5
``````
##### Sample Output 1:
``````1 1 1 2 1 3
1
``````
##### Explanation of sample input 1:
``````For test case 1:
There is exactly one path to reach 2: 1->2
There is exactly one path to reach 3: 1->3
There are two paths to reach 4: 1->4 and 1->2->4
There is exactly one path to reach 5: 1->5
There are three paths to reach 6: 1->6, 1->2->6 and 1->3->6

For test case 2:
There is only one element, therefore output will be 1.
``````
##### Sample Input 2:
``````1
7 120
2 3 4 8 5 6 10
``````
##### Sample Output 2:
``````1 0 1 2 0 1 1
``````
Console