Palindrome XOR

题意翻译

给定一个长度为 $m$ 的由 $0,1,?$ 组成的字符串 $s$，保证 $s$ 的首个字符为 $1$，现在找两个整数 $a,b$，满足： 1. $1 \leq a < b < 2^m$。 2. 在不考虑前导零的情况下，$a,b$ 的二进制表达都是回文串。 3. $a,b$ 的二进制表达按位异或的结果与 $s$ 匹配。我们称 $t$ 与 $s$ 匹配当且仅当 $t,s$ 的长度相同， $t$ 第 $i$ 个位置的字符 $t_i$ 与串 $s$ 第 $i$ 个位置的字符 $s_i$ 相同或 $s_i= \ ?$。 求这样的整数 $a,b$ 共有多少对，答案对 $998244353$ 取模。

题目描述

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

输入输出样例

输入样例 #1

10110

输出样例 #1

3

输入样例 #2

1?0???10

输出样例 #2

44

输入样例 #3

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

输出样例 #3

519569202

输入样例 #4

1

输出样例 #4

0

说明

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