'Coding has over 700 languages', '67% of programming jobs aren’t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity'

Topics

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.
```

```
You need to print your answer modulo 10^9 + 7.
```

```
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’.
```

Detailed explanation

```
1 <= T <= 10
1 <= N <= 10^3
1 <= A[i] <= 10^3
1 <= P <= 10^3
Where A[i] is array element at index ‘i’, ‘P’ is product value.
The Sum of 'N' over all test cases is <= 10 ^ 3.
Time Limit: 1 sec
```

```
2
3 8
2 3 5
4 10
15 20 30 25
```

```
4
0
```

```
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.
```

```
2
5 6
2 7 3 6 1
6 24
1 5 4 9 8 16
```

```
9
13
```

```
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.
```