Background

Verifying whether you are a real person. This may take a few seconds.

Problem Description

Little H is a bot. He has a built-in sequence $\{A_n\}$ and a binary string $H$ of length $n$. If you ask him about an interval $[l,r]$, he can give a set $g(l,r)$:

• Define a sequence $\{B_n\}$. For $i=1,2,\ldots,n$, do the following:
  • If $H_i=\tt{0}$, then $B_i=A_i$ (i.e., Little H cannot change the value of $A_i$).
  • If $H_i=\tt{1}$, he may choose any non-negative integer $v$ and set $B_i=v$ (i.e., Little H may change the value of $A_i$ arbitrarily, and the modified value does not have to be within $\boldsymbol{[0,2^k-1]}$).
• $g(l,r)=\{B_l\operatorname{xor}B_{l+1},B_{l+1}\operatorname{xor}B_{l+2},\cdots,B_{r-1}\operatorname{xor}B_{r}\}$.

Meowzai Milk needs to perform several tests on Little H. In each test, two intervals $[l,r]$ and $[L,R]$ are chosen such that $r\le L$, and Meowzai Milk asks Little H and obtains $g(l,r)$ and $g(L,R)$. If $g(l,r)\cap g(L,R)\neq\varnothing$, then the test fails, and Little H’s bot identity will be exposed.

If Little H has a strategy to answer all possible queries such that no test ever fails (that is, for any intervals $[l,r]$ and $[L,R]$ satisfying $r\le L$, the test will not fail), then we call the binary string $H$ "usable".

Given $n,k$, each term of the sequence $\{A_n\}$ is chosen independently and uniformly at random from $[0,2^k-1]$. You need to compute the expected number of "usable" binary strings $H$. Output the answer modulo $998244353$.

Input Format

A single line with two non-negative integers $n,k$, representing the length of the sequence and the size of the value range.

Output Format

A single line with one non-negative integer, representing the expected number of "usable" binary strings $H$ modulo $998244353$.

If you do not know how to take a rational number modulo:

• Let $M=998244353$. It can be proven that the answer can be written as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are positive integers and $q\not\equiv 0\pmod M$. You only need to output a non-negative integer $x\in[0,M)$ such that $x\cdot q\equiv p\pmod M$.
• If you do not know how to find such an $x$, you may refer to P2613.

1 0

2

2 1

4

3 1

499122184

5 2

655097885

10 3

972670600

114 514

802524221

Hint

Explanation for Sample 1

The only possible case is $A=[0]$. Then both $H=\tt 0$ and $H=\tt 1$ are "usable", so the answer is $2$.

Explanation for Sample 2

There are $4$ possible cases:

• $A=[0,0]$.
• $A=[0,1]$.
• $A=[1,0]$.
• $A=[1,1]$.

Without any modification, all of them can pass the test (the corresponding answers are all $2^2=4$), so the answer is $2^2=4$.

Explanation for Sample 3

There are $8$ possible cases:

• $A=[0,0,0]$, the number of valid $H$ is $7$.
• $A=[0,0,1]$, the number of valid $H$ is $8$.
• $A=[0,1,0]$, the number of valid $H$ is $7$.
• $A=[0,1,1]$, the number of valid $H$ is $8$.
• $A=[1,0,0]$, the number of valid $H$ is $8$.
• $A=[1,0,1]$, the number of valid $H$ is $7$.
• $A=[1,1,0]$, the number of valid $H$ is $8$.
• $A=[1,1,1]$, the number of valid $H$ is $7$.

When $A=[0,1,0]$, $H=\tt{000}$ is not "usable". When querying $[1,2]$ and $[2,3]$:

• Little H can only keep $A$ unchanged each time.
• When querying $[1,2]$, $g(1,2)=\{1\}$.
• When querying $[2,3]$, $g(2,3)=\{1\}$.
• $g(1,2)\cap g(2,3)=\{1\}$, so the test fails.

When $A=[1,1,1]$, $H=\tt{010}$ is "usable". When querying $[1,2]$ and $[2,3]$:

• Little H may modify the values of $A$ arbitrarily, and the modified values may be different for each query.
• When querying $[1,2]$, Little H sets $B=[1,2,1]$, so $g(1,2)=\{3\}$.
• When querying $[2,3]$, Little H sets $B=[1,1,1]$, so $g(2,3)=\{0\}$.
• $g(1,2)\cap g(2,3)=\varnothing$, so the test succeeds.

Therefore, the answer is $(7\times 4+8\times 4)\times\dfrac{1}{8}=\dfrac{15}{2}$.

Note that $2\times 499122184\equiv 15\pmod{998244353}$, so the answer is $499122184$.

Explanation for Sample 4

The answer is $\dfrac{907}{32}\equiv655097885\pmod{998244353}$.

Constraints and Notes

This problem uses bundled subtasks.

• Subtask 1 (10 pts): $n\leq2$.
• Subtask 2 (10 pts): $n\leq 6$ and $k\leq 2$.
• Subtask 3 (10 pts): $n\leq 50$ and $k\leq6$.
• Subtask 4 (10 pts): $n\leq 500$ and $k\leq 20$.
• Subtask 5 (20 pts): $n\leq 2\times10^3$.
• Subtask 6 (20 pts): $n\leq 5\times10^4$.
• Subtask 7 (20 pts): no special restrictions.

For all testdata, $1\leq n\leq 10^6$ and $0\leq k\leq 10^9$.

Translated by ChatGPT 5