1147D · Palindrome XOR

Problem: 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 Format: 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 Format: Print a single integer, the count of pairs that satisfy the conditions modulo $998244353$.

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