题目描述

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

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

输入格式

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

$S$

输出格式

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

输入输出样例 #1

输入 #1

0001

输出 #1

8

输入输出样例 #2

输入 #2

110001

输出 #2

24

输入输出样例 #3

输入 #3

11101111011111000000000110000001111100011111000000001111111110000000111111111

输出 #3

697354558

说明/提示

限制

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

样例解释 1

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