{"raw_statement":[{"iden":"problem statement","content":"> The definition of a good pair of sequences in this problem is the same as in Problem D.\n\nA pair of sequences of length $M$ consisting of positive integers at most $N$, $(S, T) = ((S_1, S_2, \\dots, S_M), (T_1, T_2, \\dots, T_M))$, is said to **be a good pair of sequences** when $(S, T)$ satisfies the following condition.\n\n*   There exists a sequence $X = (X_1, X_2, \\dots, X_N)$ of length $N$ consisting of $0$ and $1$ that satisfies the following condition:\n    *   $X_{S_i} \\neq X_{T_i}$ for each $i=1, 2, \\dots, M$.\n\nAmong the $N^{2M}$ possible pairs of sequences of length $M$ consisting of positive integers at most $N$, $(A, B) = ((A_1, A_2, \\dots, A_M), (B_1, B_2, \\dots, B_M))$, find the number, modulo $998244353$, of those that are good pairs of sequences."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 30$\n*   $1 \\leq M \\leq 10^9$\n*   $N$ and $M$ are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$"},{"iden":"sample input 1","content":"3 2"},{"iden":"sample output 1","content":"36\n\nFor example, if $A=(1,2), B=(2,3)$, then $(A, B)$ is a good pair of sequences. Indeed, if we set $X=(0,1,0)$, then $X$ is a sequence of length $N$ consisting of $0$ and $1$ that satisfies $X_{A_1} \\neq X_{B_1}$ and $X_{A_2} \\neq X_{B_2}$. Thus, $(A, B)$ satisfies the condition of being a good pair of sequences.  \nThere are a total of $36$ good pairs of sequences, so print this number."},{"iden":"sample input 2","content":"3 3"},{"iden":"sample output 2","content":"168"},{"iden":"sample input 3","content":"12 34"},{"iden":"sample output 3","content":"539029838"},{"iden":"sample input 4","content":"20 231104"},{"iden":"sample output 4","content":"966200489"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}