3836: Blank

There are N blanks arranged in a row. The blanks are numbered 1,2,...,N from left to right. Tom is filling each blank with one number in {0,1,2,3}. According to his thought, the following M conditions must all be satisfied. The ith condition is: There are exactly xi different numbers among blanks ∈ [li,ri]. Inhowmanywayscantheblanksbefilledtosatisfyalltheconditions?Findtheanswermodulo 998244353.

The first line of the input contains an integer T(1 ≤ T ≤ 15), denoting the number of test cases. In each test case, there are two integers n(1 ≤ n ≤ 100) and m(0 ≤ m ≤ 100) in the first line, denoting the number of blanks and the number of conditions. For the following m lines, each line contains three integers l,r and x, denoting a condition(1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 4).

For each testcase, output a single line containing an integer, denoting the number of ways to paint the blanks satisfying all the conditions modulo 998244353.

2 
1 0 
4 1 
1 3 3

4
96