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 \lt b \lt 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$.

给你一个由字符 "1"、"0" 和 "?" 组成的字符串 $s$，其中 $s$ 的第一个字符保证为 "1"。设 $m$ 为字符串 $s$ 的长度。

请计算满足以下条件的整数对 $(a, b)$ 的个数：

• $1 \leq a \lt b \lt 2^m$；
• $a$ 和 $b$ 的二进制表示（不含前导零）均为回文串；
• $a$ 与 $b$ 的按位异或（XOR）结果的二进制表示与模式 $s$ 匹配。我们称字符串 $t$ 与 $s$ 匹配，当且仅当 $t$ 与 $s$ 长度相同，且对每个下标 $i$，$t$ 的第 $i$ 个字符等于 $s$ 的第 $i$ 个字符，或者 $s$ 的第 $i$ 个字符为 "?"。

请将该计数值对 $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".

第一行包含一个字符串 $s$（$1 \leq |s| \leq 1\,000$）。$s$ 仅由字符 "1"、"0" 和 "?" 组成。保证 $s$ 的第一个字符为 "1"。

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

输出一个整数，即满足条件的数对个数对 $998244353$ 取模的结果。

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

对于第一个例子，二进制下的数对为 $(111, 10001), (11, 10101), (1001, 11111)$。