The Cypriote Mermaid

Time limit1sMemory limit2048 MB

Summary

Count the ways to fill each ? in a 0/1 string so that repeatedly removing adjacent equal pairs empties it, modulo 998244353.

Level: Medium6 of 10
Topics: Combinatorics, String, Math
Solved: No attempts yet

Problem

Every summer, Stelinuța goes to Cyprus for an 11-day programming camp. While she is there, she likes to swim and snorkel in the sea.

One day, while snorkeling, she found a very interesting pearl necklace: a straight (non-cyclic) thread with pearls on it. Originally, every pearl was either black or white. However, some pearls were so damaged that she could not tell their original color.

Stelinuța then came up with an idea. Suppose you can remove any two adjacent pearls that have the same color from the necklace. How many different ways could the original necklace have looked so that, after applying this operation any number of times, she can end up with an empty necklace? Since the answer may be very large, print it modulo $998\,244\,353$ .

Input

The first line contains a string of 1, 0, and ?, describing the necklace Stelinuța found. Each pearl is represented as follows:

1: the pearl is black,
0: the pearl is white,
?: the original color is unknown.

The length of the string is at least 1 and at most $2 \cdot 10^{5}$ .

Output

Output a single integer: the number of different ways the necklace could have looked, modulo $998\,244\,353$ .

Hint

In the sample, the only possible necklace is 011110. Remove 11 twice, then remove the remaining 00 to get an empty necklace. For all other assignments, there is no way to remove every pearl by repeatedly removing two adjacent pearls of the same color.

Examples1

Example 1
Input
```
01?1??
```
Expected output
```
1
```