Score : $1000$ points

Problem Statement

PCT made the following problem.

Xor Optimization ProblemYou are given a sequence of non-negative integers of length $N$: $A_1,A_2,...,A_N$. When it is allowed to choose any number of elements in $A$, what is the maximum possible $\mathrm{XOR}$ of the chosen values?

Nyaan thought it was too easy and revised it to the following.

Many Xor Optimization ProblemsThere are $2^{NM}$ sequences of length $N$ consisting of integers between $0$ and $2^M-1$. Find the sum, modulo $998244353$, of the answers to Xor Optimization Problem for all those sequences.

Solve Many Xor Optimization Problems.

Constraints

• $1 \le N,M \le 250000$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

Output

Print the answer.

2 1

3

We are to solve Xor Optimization Problem for all sequences of length $2$ consisting of integers between $0$ and $1$.

• The answer for $A=(0,0)$ is $0$.
• The answer for $A=(0,1)$ is $1$.
• The answer for $A=(1,0)$ is $1$.
• The answer for $A=(1,1)$ is $1$.

Thus, the final answer is $0+1+1+1=3$.

3 4

52290

1234 5678

495502261