{"raw_statement":[{"iden":"problem statement","content":"Print the number, modulo $998244353$, of permutations $P=(P_1,P_2,\\dots,P_N)$ of $(1,2,\\dots,N)$ that satisfy all of the following conditions:\n\n*   $\\max(P_{A_i},P_{B_i}) = C_i\\ (1 \\le i \\le M)$."},{"iden":"constraints","content":"*   $2 \\le N \\le 2 \\times 10^5$\n*   $1 \\le M \\le 2 \\times 10^5$\n*   $1 \\le A_i < B_i \\le N$\n*   $1 \\le C_i \\le N$\n*   $(A_i,B_i) \\neq (A_j,B_j)$ if $i \\neq j$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$\\vdots$\n$A_M$ $B_M$ $C_M$"},{"iden":"sample input 1","content":"4 2\n1 2 4\n2 3 2"},{"iden":"sample output 1","content":"2\n\nThe two permutations $P$ that satisfy the conditions are $(4,1,2,3)$ and $(4,2,1,3)$."},{"iden":"sample input 2","content":"6 3\n1 4 3\n2 5 6\n3 4 2"},{"iden":"sample output 2","content":"8"},{"iden":"sample input 3","content":"20 17\n9 16 13\n5 14 20\n15 20 14\n5 13 17\n18 20 14\n14 20 20\n6 13 11\n12 16 19\n2 15 10\n6 17 11\n7 18 7\n8 18 12\n8 16 13\n6 16 13\n2 18 10\n9 10 15\n7 14 20"},{"iden":"sample output 3","content":"1209600"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}