Problem Description

Please note the unusual time limit.

Xiao C has a complete binary tree with $dep$ levels and $n$ nodes. She wants to choose a connected block that includes the root node to color. She wonders how many different coloring schemes there are, with the answer modulo $998,244,353$.

Input Format

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

For each test case:

The first line contains an integer $dep$, as described in the problem.

The second line contains an integer $s$, representing the number of leaf nodes at the lowest level. Specifically, $s$ is represented as a $dep$-bit binary string, which you will read. If the binary representation of $s$ is less than $dep$ bits, it will be prefixed with zeros.

The data is guaranteed to be valid.

Output Format

For each test case, output a single integer on a new line, representing the number of valid coloring schemes.

Sample Input and Output

Input Sample #1

1
2
10

Output Sample #1

4

Input Sample #2

1
3
100

Output Sample #2

25

Input Sample #3

1
3
010

Output Sample #3

10

Input Sample #4

See attachment

Output Sample #4

See attachment

Notes

You can learn about the terms used in the problem by studying OI-Wiki Tree Basics.

Sample Explanation

For Sample #1, the binary tree can be drawn as follows:

We number the nodes of the binary tree using pre-order traversal (as shown in the figure), resulting in the set $\left(1,2,3\right)$.

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

For Sample #3, the binary tree can be drawn as follows:

We number the nodes of the binary tree using pre-order traversal (as shown in the figure), resulting in the set $\left(1,2,3,4,5\right)$.

Thus, 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.

Clearly, $\left(2,3,4\right),\left(1,3,4\right)$ are not valid coloring schemes, as the former does not include the root node, and the latter does not form a connected set of nodes.

Data Constraints

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

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

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

见题面 Input 部分

见题面 Output 部分