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 10⁹ + 7.
• No need to handle input/output as it's taken care of; implement the function directly.