← 返回题目列表

Codeforces · 1147/D

D. 回文异或

中文机器翻译题面 查看原题

给定一个由字符“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)$$$。