Problem Description

Little A is playing a game called "Truth or Lie" on his computer.

At the beginning of the game, the computer provides $n$ statements, each in the form of "Statement $x$ is true" or "Statement $x$ is false", where $x$ is an integer between $1$ and $n$. You just need to choose "Good" or "Bad". "Good" means you can determine the truth or falsehood of each statement so that each statement's content holds true, while "Bad" means the opposite.

As a newbie, Little A keeps clicking "Good" and relies on luck to pass the levels.

After countless failures, Little A, who is from Africa, discovered that in each level of the game, whether each statement contains "true" or "false" is fixed, but the $x$ in each statement is uniformly random between $1$ and $n$.

Now, Little A has told you the truth or falsehood of each statement in a level, represented by a $01$ sequence. The $i$-th bit being $0$ means the $i$-th statement contains "false", otherwise it contains "true". He wants to know the number of ways to correctly click "Good".

Since the number of ways might be very large, you need to output the result modulo $998244353$.

(If you don't understand the problem, please refer to the sample explanation)

Input Format

A single line containing a $01$ sequence, where the length of the sequence is $n$.

Output Format

Output the number of ways modulo $998244353$.

Sample Input and Output

Sample Input #1

01

Sample Output #1

1

Sample Input #2

10101

Sample Output #2

1154

Sample Input #3

10101101010111110100110100101010110001010010101001

Sample Output #3

322173207

Notes

Sample Explanation

The first statement's content is "Some statement is false", and the second statement's content is "Some statement is true". All possible scenarios are as follows:

1. The first statement's content is "The first statement is false", and the second statement's content is "The first statement is true", the result should be Bad.

2. The first statement's content is "The first statement is false", and the second statement's content is "The second statement is true", the result should be Bad.

3. The first statement's content is "The second statement is false", and the second statement's content is "The first statement is true", the result should be Bad.

4. The first statement's content is "The second statement is false", and the second statement's content is "The second statement is true", the result should be Good, because you can just consider the first statement as false and the second statement as true, which satisfies both statements, so it is Good.

Therefore, there is only one valid scheme.

Data Range

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

见题面 Input 部分

见题面 Output 部分