Palindrome XOR

1000ms

262144K

Description:

You are given a string $$$s$$$ consisting of characters "1", "0", and "?". The first character of $$$s$$$ is guaranteed to be "1". Let $$$m$$$ be the number of characters in $$$s$$$.

Count the number of ways we can choose a pair of integers $$$a, b$$$ that satisfies the following:

$$$1 \leq a < b < 2^m$$$
When written without leading zeros, the base-2 representations of $$$a$$$ and $$$b$$$ are both palindromes.
The base-2 representation of bitwise XOR of $$$a$$$ and $$$b$$$ matches the pattern $$$s$$$. We say that $$$t$$$ matches $$$s$$$ if the lengths of $$$t$$$ and $$$s$$$ are the same and for every $$$i$$$, the $$$i$$$-th character of $$$t$$$ is equal to the $$$i$$$-th character of $$$s$$$, or the $$$i$$$-th character of $$$s$$$ is "?".

Compute this count modulo $$$998244353$$$.

Input:

The first line contains a single string $$$s$$$ ($$$1 \leq |s| \leq 1\,000$$$). $$$s$$$ consists only of characters "1", "0" and "?". It is guaranteed that the first character of $$$s$$$ is a "1".

Output:

Print a single integer, the count of pairs that satisfy the conditions modulo $$$998244353$$$.

Sample Input:

Sample Output:

Sample Input:

1?0???10

Sample Output:

Sample Input:

1?????????????????????????????????????

Sample Output:

519569202

Sample Input:

Sample Output:

Note:

For the first example, the pairs in base-2 are $$$(111, 10001), (11, 10101), (1001, 11111)$$$.

Informação

Provedor Codeforces

Código CF1147D