Description

Xiao A is playing a game on the computer called Truth or Lie.

At the start of the game, the computer gives $n$ sentences. Each sentence is of the form “Statement $x$ is true” or “Statement $x$ is false,” where $x$ is an integer from $1$ to $n$. You only need to choose either "Good" or "Bad." "Good" means that you can determine the truth value of each statement so that the content of every sentence holds. "Bad" means the opposite.

As a newbie, Xiao A keeps clicking "Good" and hopes to pass by luck.

After countless failures, Xiao A discovers that in each level, whether a sentence contains the word “true” or “false” is fixed, but the $x$ in each sentence is chosen uniformly at random from $1$ to $n$.

Now Xiao A tells you, for a certain level, which word each sentence contains, represented by a $01$ sequence. The $i$-th bit being $0$ means the $i$-th sentence contains “false,” otherwise it contains “true.” He wants to know the number of assignments of the $x$’s that make clicking "Good" correct.

Since the number of valid assignments may be large, you need to output the result modulo $998244353$.

(If you do not understand the problem, please refer to the sample explanation.)

Input Format

A single line containing a $01$ sequence, whose length is $n$.

Output Format

Output the number of valid assignments modulo $998244353$.

01

1

10101

1154

10101101010111110100110100101010110001010010101001

322173207

Hint

Sample Explanation

The first sentence says “Some statement is false,” and the second sentence says “Some statement is true.” All possible cases are as follows:

1. The first sentence says “Statement 1 is false,” the second says “Statement 1 is true.” The result should be Bad.
2. The first sentence says “Statement 1 is false,” the second says “Statement 2 is true.” The result should be Bad.
3. The first sentence says “Statement 2 is false,” the second says “Statement 1 is true.” The result should be Bad.
4. The first sentence says “Statement 2 is false,” the second says “Statement 2 is true.” The result should be Good, because setting the first statement to false and the second statement to true satisfies both sentences, so it is Good.

Therefore, there is exactly one valid assignment.

Constraints

• For $10\%$ of the testdata, $n \leq 7$.
• For $20\%$ of the testdata, $n \leq 9$.
• For $60\%$ of the testdata, $n \leq 20$.
• For $100\%$ of the testdata, $1 \leq n \leq 50$.

Translated by ChatGPT 5