Background

[Image deleted by March.]

Takizawa March Orz.

The deleted image will be secretly shown to the students who sign up for the editorial session (

Problem Description

Please note the unusual time limit.

Little C has a complete binary tree with $dep$ levels and $n$ nodes. She wants to choose one connected subgraph that contains the root node and color it. She wants to know how many different coloring schemes there are. Output the answer modulo $998,244,353$.

Input Format

Multiple test cases. The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains an integer $dep$, as described above.

The second line contains an integer $s$, the number of leaf nodes on the bottom level. In particular, it will be given in binary: you will read a $dep$-bit $\texttt{01}$ string to represent $s$. If the binary representation has fewer than $dep$ bits, it is padded with leading $0$.

It is guaranteed that the input is valid.

Output Format

For each test case, output one integer per line, the number of valid coloring schemes. A newline is required.

1
2
10

4

1
3
100

25

1
3
010

10

见附件

见附件

Hint

You can learn the terms used in this statement by reading OI-Wiki Tree Basics.

[Sample Explanation]

For sample #1, you can draw the following binary tree.

We label this binary tree in preorder traversal (as shown in the figure), obtaining the vertex set $\left(1,2,3\right)$.

Then only $\left(1,2,3\right),\left(1,2\right),\left(1,3\right),\left(1\right)$ are valid coloring schemes.

For sample #3, you can draw the following binary tree.

We label this binary tree in preorder traversal (as shown in the figure), obtaining the vertex set $\left(1,2,3,4,5\right)$.

Then only $\left(1,2,3,4,5\right),\left(1,2,3,4\right),\left(1,2,3\right),\left(1,2,4\right),\left(1,2\right),\left(1,2,3,5\right),\left(1,2,4,5\right),\left(1,2,5\right),\left(1,5\right),\left(1\right)$ are valid coloring schemes.

Obviously, $\left(2,3,4\right)$ and $\left(1,3,4\right)$ are not valid coloring schemes: the former does not include the root node, and the latter is not connected.

For $30\%$ of the testdata, $1\leq T\leq 10, 1\leq dep \leq 20$.

For another $20\%$ of the testdata, the tree is a full binary tree (i.e. a perfect binary tree).

For $100\%$ of the testdata, $1\leq T\leq 10, 1\leq dep \leq 10^6$.

Input Format

Output Format

Hint

Translated by ChatGPT 5