 4

# Count Number of Subsequences

Difficulty: MEDIUM Contributed By
Shrey Pansuria
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

#### Given an array of non-negative integers ‘A’ and an integer ‘P’, find the total number of subsequences of ‘A’ such that the product of any subsequence should not be more than ‘P’.

``````A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
``````
##### Note
``````You need to print your answer modulo 10^9 + 7.
``````
##### For Example
``````Let us take  A = [1,2,3] and P = 4.
All the subsequences not having product more than ‘4’ are {1}, {2}, {3}, {1,2}, {1,3}. Therefore count is equal to ‘5’.
``````
##### Input Format
``````The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains two integers, ‘N’-number of elements in the array and ‘P’.

The second line of each test case contains ‘N’ space-separated integers that make up ‘A’.
``````
##### Output Format
``````For each test case, Print an integer denoting the count of subsequences not having a product more than ‘P’.

Print the output of each test case in a separate line.
``````
##### Note
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints
``````1 <= T <= 50
1 <= N <= 10^3
1 <= A[i] <= 10^3
1 <= P <= 10^8

Where A[i] is array element at index ‘i’,  ‘P’ is product value.

Time Limit: 1 sec
``````
##### Sample Input 1:
``````2
3 8
2 3 5
4 10
15 20 30 25
``````
##### Sample Output 1:
``````4
0
``````
##### Explanation For Sample Input 1:
``````Test Case 1: The given array is [2,3,5].
All the possible subsequences of this array are {2}, {3}, {5}, {2,3}, {2,5}, {3,5}, {2,3,5}. But product of elements of subsequence {2,5}, {3,5}, {2,3,5} is more than p i.e 8. Therefore required count is 4.

Test Case 2: The given array is [15, 20. 30, 25] and p=10.
As all the subsequences have product more than10’. So answer equals 0.
``````
##### Sample Input 2
``````2
5 6
2 7 3 6 1
6 24
1 5 4 9 8 16
``````
##### Sample Output 2
``````9
13
``````
##### Explanation For Sample Input 2:
``````Test Case 1: The given array is [2, 7, 3, 6, 1].
The total number of subsequences having product less than 6 are 9.

Test Case 2: The given array is [1, 5, 4, 9, 8, 16]
The total number of subsequences having product less than 24 are 13.
``````   Console