CF1147D.Palindrome XOR

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$ .

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".

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

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