Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

LCM Divisible Subsequence

By flash_7 · Limits 5s, 512 MB

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

InputOutput
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:

  1. 2, 4 (LCM = 4, which is divisible by 2)
  2. 2, 3 (LCM = 6, which is divisible by 2)
  3. 3, 4 (LCM = 12, which is divisible by 2)

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:

  1. 2, 8, 12 (LCM = 24, which is divisible by 6)
  2. 2, 12, 6 (LCM = 12, which is divisible by 6)
  3. 8, 12, 6 (LCM = 24, which is divisible by 6)

Discussion

Statistics


100% Solution Ratio

steinumEarliest, 2w ago

steinumFastest, 0.1s

steinumLightest, 918 kB

steinumShortest, 1447B

Submit

Login to submit