You have just learned the algorithm bubble sort, which is able to sort an array in non-descending order. Let's define the function $$$\text{sort}(a)$$$ as in the following pseudocode:

function sort(array a):
    rounds := 0
    n := length of a
    while a is not non-decreasing:
        rounds := rounds + 1
        for i from 1 to n - 1:
            if a[i] > a[i + 1]:
                swap(a[i], a[i + 1])
    return rounds

As it is shown, the return value of $$$\text{sort}(a)$$$ represents the number of rounds needed to make array $$$a$$$ sorted in non-descending order by using bubble sort.

You are given an integer $$$n$$$, as well as $$$m$$$ integer tuples $$$(k_i,l_i,r_i)$$$ ($$$1\le i\le m$$$). Count the number of permutations$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$, modulo $$$998\,244\,353$$$, so that the following restrictions are satisfied:

For each $$$1\le i\le n$$$, let $$$b_i=\text{sort}([p_1,p_2,\ldots,p_{i}])$$$, then
For each $$$1\le j\le m$$$, let $$$x$$$ be the number of indices $$$y$$$ ($$$1\le y\le n$$$) such that $$$b_y\le k_j$$$, then $$$l_j\le x\le r_j$$$ holds.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2\leq n\leq 10^6$$$, $$$0\leq m\leq 1000$$$).

Then $$$m$$$ lines follow, the $$$i$$$-th line containing three integers $$$k_i$$$, $$$l_i$$$, and $$$r_i$$$ ($$$0\le k_i\le n - 1$$$, $$$1\le l_i\le r_i\le n$$$) — the restrictions.

It is guaranteed that the sum of $$$m^2$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer — the number of possible permutations, modulo $$$998\,244\,353$$$.

Note

In the first test case, only permutations $$$[3,1,4,2]$$$ and $$$[4,1,3,2]$$$ satisfy the restrictions. Take $$$[3,1,4,2]$$$ as an example. Let's calculate the array $$$b$$$:

$$$\text{sort}([3])=0$$$;
$$$\text{sort}([3,1])=1$$$;
$$$\text{sort}([3,1,4])=1$$$;
$$$\text{sort}([3,1,4,2])=2$$$.

Thus, $$$b=[0,1,1,2]$$$. It is easy to show that it satisfies all the restrictions.

In the second test case, only permutation $$$[1,2,3]$$$ satisfies the restrictions.

In the third test case, the following $$$8$$$ permutations satisfy the restrictions:

$$$[2,3,1,4]$$$;
$$$[2,4,1,3]$$$;
$$$[3,2,1,4]$$$;
$$$[3,4,1,2]$$$;
$$$[3,4,2,1]$$$;
$$$[4,2,1,3]$$$;
$$$[4,3,1,2]$$$;
$$$[4,3,2,1]$$$.

Bubble Sort

Examples