Relay Stations in the Mountains

There are $N$ mountains in a row, numbered from left to right. The height of mountain $i$ is $h_i$.

King Dadas chooses exactly $K$ distinct mountains and installs one relay station on each chosen mountain.

Suppose $i<j$ and relay stations are installed on mountains $i$ and $j$. The two relay stations can communicate directly if

If $i$ and $j$ are adjacent positions, their relay stations can always communicate directly.

Construct an undirected graph whose vertices are the installed relay stations and whose edges connect pairs that can communicate directly. Every pair of relay stations must be able to exchange information through at most $D$ edges. Equivalently, the graph must be connected and have diameter at most $D$. The diameter of a graph with one vertex is defined as $0$.

Count the valid ways to install the relay stations. Two ways are different if their sets of chosen mountains are different.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N\ K\ D$ $h_1\ h_2\ \cdots\ h_N$

For each test case, print the number of valid installations modulo $998\,244\,353$ on one line.

• $1 \leq T \leq 100$.
• $1 \leq K \leq N \leq 100\,000$.
• $1 \leq D \leq 100$.
• $1 \leq h_i \leq N$ ($1 \leq i \leq N$).
• The sum of $N$ over all test cases does not exceed $100\,000$.