给定一个由字符“1”、“0”和“?”组成的字符串 $$$s$$$。 $$$s$$$ 的第一个字符保证为“1”。令 $$$m$$$ 为 $$$s$$$ 中的字符数。
计算我们可以选择满足以下条件的一对整数 $$$a, b$$$ 的方式数:
- $$$1 \leq a < b < 2^m$$$
- 当不带前导零写入时, $$$a$$$ 和 $$$b$$$ 的基数 2 表示形式都是回文。
- $$$a$$$ 和 $$$b$$$ 的按位异或的以 2 为基数表示与模式 $$$s$$$ 匹配。如果 $$$t$$$ 和 $$$s$$$ 的长度相同,并且对于每个 $$$i$$$,$$$t$$$ 的第 $$$i$$$ 字符等于 $$$s$$$ 的第 $$$i$$$ 字符,或者 $$$s$$$ 的第 $$$i$$$ 字符是 $$$t$$$ 与 $$$s$$$ 匹配。 “?”。
计算此计数模 $$$998244353$$$。
输入
第一行包含单个字符串 $$$s$$$ ($$$1 \leq |s| \leq 1\,000$$$)。 $$$s$$$ 仅由字符“1”、“0”和“?”组成。保证 $$$s$$$ 的第一个字符是“1”。
输出
打印一个整数,即满足条件对 $$$998244353$$$ 取模的对的计数。
示例
输入 #1
10110
输出 #1
3
输入 #2
1?0???10
输出 #2
44
输入 #3
1?????????????????????????????????????
输出 #3
519569202
输入#4
1
输出#4
0
注意
对于第一个示例,base-2 中的对是 $$$(111, 10001), (11, 10101), (1001, 11111)$$$。