{"problem":{"name":"Ex - Balance Scale","description":{"content":"There are $N$ weights numbered $1,2, \\dots,N$.   Using a balance, we will compare weights $M$ times. *   Before the comparisons, prepare an empty string $S$. *   For the $i$\\-th comparison, put just ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc306_h"},"statements":[{"statement_type":"Markdown","content":"There are $N$ weights numbered $1,2, \\dots,N$.  \nUsing a balance, we will compare weights $M$ times.\n\n*   Before the comparisons, prepare an empty string $S$.\n*   For the $i$\\-th comparison, put just weight $A_i$ to the left bowl, and just weight $B_i$ to the right.\n*   Then, one of the following three results is obtained.\n    *   If weight $A_i$ is heavier than weight $B_i$,\n        *   append `>` to the tail of $S$.\n    *   If weight $A_i$ and weight $B_i$ have the same mass,\n        *   append `=` to the tail of $S$.\n    *   If weight $A_i$ is lighter than weight $B_i$,\n        *   append `<` to the tail of $S$.\n*   The result is always accurate.\n\nAfter the experiment, you will obtain a string $S$ of length $M$.  \nAmong the $3^M$ strings of length $M$ consisting of `>`, `=`, and `<`, how many can be obtained as $S$ by the experiment?  \nSince the answer can be enormous, print the answer modulo $998244353$.\n\n## Constraints\n\n*   All input values are integers.\n*   $2 \\le N \\le 17$\n*   $1 \\le M \\le \\frac{N \\times (N-1)}{2}$\n*   $1 \\le A_i < B_i \\le N$\n*   $i \\neq j \\Rightarrow (A_i,B_i) \\neq (A_j,B_j)$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_M$ $B_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc306_h","tags":[],"sample_group":[["3 3\n1 2\n1 3\n2 3","13\n\nLet $w$ be the sequence of the mass of the weights, in ascending order of weight numbers.\n\n*   If $w=(5,5,5)$, you obtain $S=$ `===`.\n*   If $w=(2,2,3)$, you obtain $S=$ `=<<`.\n*   If $w=(6,8,6)$, you obtain $S=$ `<=>`.\n*   If $w=(9,4,4)$, you obtain $S=$ `>>=`.\n*   If $w=(7,7,3)$, you obtain $S=$ `=>>`.\n*   If $w=(8,1,8)$, you obtain $S=$ `>=<`.\n*   If $w=(5,8,8)$, you obtain $S=$ `<<=`.\n*   If $w=(1,2,3)$, you obtain $S=$ `<<<`.\n*   If $w=(4,9,5)$, you obtain $S=$ `<<>`.\n*   If $w=(5,1,8)$, you obtain $S=$ `><<`.\n*   If $w=(6,9,2)$, you obtain $S=$ `<>>`.\n*   If $w=(7,1,3)$, you obtain $S=$ `>><`.\n*   If $w=(9,7,5)$, you obtain $S=$ `>>>`.\n\nWhile there is an infinite number of possible sequences of the mass of the weights, $S$ is always one of the $13$ above."],["4 4\n1 4\n2 3\n1 3\n3 4","39"],["14 15\n1 2\n1 3\n2 4\n2 5\n2 6\n4 8\n5 6\n6 8\n7 8\n9 10\n9 12\n9 13\n10 11\n11 12\n11 13","1613763"]],"created_at":"2026-03-03 11:01:14"}}