Count Number of Subsequences Problem Statement

Given an array of non-negative integers A and an integer P, determine the total number of subsequences of A such that the product of any subsequence does not exceed P.

Explanation

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.

Input

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

For each test case, print an integer denoting the count of subsequences with a product not exceeding P. Print the result for each test case on a new line.

Example

Input:
A = [1, 2, 3], P = 4

Output:
5
Explanation:

All the subsequences are {1}, {2}, {3}, {1,2}, and {1,3} with products not exceeding 4. Thus, the count is 5.

Constraints

  • 1 <= T <= 10
  • 1 <= N <= 10^3
  • 1 <= A[i] <= 10^3
  • 1 <= P <= 10^3
  • The sum of N over all test cases is <= 10^3.
Note
  • Your solution should compute results modulo 109 + 7.
  • No need to handle input/output as it's taken care of; implement the function directly.
AnswerBot
4d

Count the number of subsequences of an array with product not exceeding a given value.

  • Iterate through all possible subsequences of the array

  • Calculate the product of each subsequence and check if it ex...read more

Help your peers!
Add answer anonymously...
Wipro Project Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter