Description

IA is a girl who can sing.

IOI 2018 is coming, and IA decides to write a song for the contestants to express her best wishes. The song has $n$ notes, and the pitch of the $i$-th note is $h_i$. IA's vocal range is $A$, and she can only sing positive integer pitches in $1\sim A$. Therefore $1\le h_i\le A$.

Before composing, IA needs to decide the structure of the song, so she wrote down $Q$ constraints, where the $i$-th constraint is: among the notes indexed from $l_i$ to $r_i$, the maximum pitch is $m_i$. After the structure is fixed, she can start composing. However, she still wants to know how many possible songs satisfy all her constraints. She heard you will go to IOI in 9 months, so she hopes you can help her compute this value.

Input Format

Read from standard input.

The first line contains an integer $T$ ($T\le 20$), the number of testdata groups.

For each group, the first line contains three positive integers $n, Q, A$. Then follow $Q$ lines, each with three integers $l_i, r_i, m_i$, representing one constraint. It is guaranteed that $1\le l_i\le r_i\le n, 1\le m_i\le A$.

Output Format

Write to standard output.

Output a single line indicating the number of possible songs. Since this number can be large, output the answer modulo $998244353$.

1
3 2 3
1 2 3
2 3 2

3

2
4 2 4
1 2 3
2 3 4
7 3 74
3 6 56
2 5 56
3 7 70

20
160326468

Hint

Explanation for Sample 1. The following are the three possible songs: $(3, 1, 2)$, $(3, 2, 1)$, $(3, 2, 2)$.

Translated by ChatGPT 5