P8089 "JROI-5" Color

[Image deleted by March.] Takizawa March Orz. --- The deleted image will be secretly shown to the students who sign up for the editorial session (

**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$.

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.**

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

You can learn the terms used in this statement by reading [OI-Wiki Tree Basics](https://oi-wiki.org/graph/tree-basic/). [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