题目描述

给定一个只包含 0 和 1 的字符串 $S$。请你求出通过以下操作任意次（包括 $0$ 次）后，可能得到的不同字符串的个数，并对 $998244353$ 取模。

• 移除 $S$ 的前两个字符，从中丢弃一个，将另一个插入到 $S$ 的任意位置。该操作仅当 $S$ 长度不少于 $2$ 时才能执行。

输入格式

输入为标准输入，格式如下：

$S$

输出格式

输出通过 $0$ 次或多次操作后，可能得到的不同字符串的个数，对 $998244353$ 取模。

样例 1

输入

0001

输出

8

样例 2

输入

110001

输出

24

样例 3

输入

11101111011111000000000110000001111100011111000000001111111110000000111111111

输出

697354558

说明/提示

限制

• $1 \leq |S| \leq 300$
• $S$ 仅由 0 和 1 组成

样例解释 1

可以得到的字符串有：0001、001、010、00、01、10、0、1，共 $8$ 个。

由 ChatGPT 4.1 翻译