CF1147D Palindrome XOR

给定一个由字符 “1”、“0” 和 “?” 组成的字符串 $s$。保证 $s$ 的第一个字符为 “1”。设 $m$ 为 $s$ 的长度。 请你统计有多少对整数 $a, b$ 满足以下条件： - $1 \leq a < b < 2^m$； - $a$ 和 $b$ 的二进制表示（不含前导零）都是回文串； - $a$ 和 $b$ 按位异或后的二进制表示与 $s$ 匹配。这里称 $t$ 与 $s$ 匹配，指的是 $t$ 和 $s$ 长度相同，且对于每个 $i$，$t$ 的第 $i$ 个字符等于 $s$ 的第 $i$ 个字符，或者 $s$ 的第 $i$ 个字符为 “?”。 请你输出满足条件的对数，答案对 $998244353$ 取模。

第一行输入一个字符串 $s$（$1 \leq |s| \leq 1000$），仅包含 “1”、“0” 和 “?”。保证 $s$ 的第一个字符为 “1”。

输出一个整数，表示满足条件的对数，对 $998244353$ 取模。

对于第一个样例，满足条件的二进制对为 $(111, 10001), (11, 10101), (1001, 11111)$。 由 ChatGPT 4.1 翻译