LCM Divisible Subsequence
You’ll be given an array of $N$ integers and two more integers $K$ and $M$. You have to find the number of lcm divisible subsequence of length $M$ in that array.
A subsequence of length $M$ is called lcm divisible subsequence if the LCM (Lowest Common Multiple) of all the numbers in that subsequence is divisible by $K$. For example, if $A = [2, 2, 3, 4, 7, 6]$, $M = 3$ and $K = 6$, then $(2, 2, 6)$ is a valid lcm divisible subsequence. Because the length of this subsequence is $M = 3$ and the LCM is $6$, which is divisible by $K = 6$.
Note: A subsequence in the array $A$ is a sequence that can be derived by deleting some or no elements without changing the order of the remaining elements in the array $A$. Two subsequences are considered different if the chosen indices are different.
Constraints
$1 \leq T \leq 5 $$1 \leq N \leq 100000 $$1 \leq M \leq 1000 $$1 \leq K, A_i \leq 50000 $
Input
The first line of the input contains a single integer $T$ denoting the number of test cases, then $T$ test cases follow. The first line of a test case contains three integers $N$, $M$ and $K$. The following line of the test case contains $N$ space separated integers of the array $A$.
Output
For each test case print a single integer, the number of lcm divisible subsequence in the given array. Since the answer can be quite large, you have to compute it modulo $998244353$.
Sample
| Input | Output |
|---|---|
5 3 2 2 2 3 4 4 3 9 2 4 5 6 5 3 6 2 8 12 5 6 6 3 6 2 2 3 4 7 6 10 3 6 2 3 6 12 16 18 20 25 9 24 | 3 0 9 16 115 |
In the first test case, the list of valid lcm divisible subsequence is given below:
In the second test case, there's no valid lcm divisible subsequence. In the third test case, some valid lcm divisible subsequences are given below:
| |
