给定一个字符串s,里面全都是由 '5'、'2' 和 '0' 组成,这个字符串内总计有 520 个为 "520" 的子序列。现在字符串中将某些部分换成‘?‘,再将'?'部分换成 '5'、'2' 和 '0',在所有可能的字符串中,位置不同的为 "520" 的子序列共有多少个?答案会很大,所以请你模 998244353 返回
示例1

输入

"552200"

输出

8

说明

显然,这个字符串共有 8 个子序列为 520。
示例2

输入

"5?0"

输出

1

说明

把中间这个 ? 替换为 2 后我们得到一个子序列为 520,其他情况均没有 520。
示例3

输入

"5?2?0"

输出

8
示例4

输入

"?????"

输出

10

备注:
某个字符串的子序列指的是去掉这个字符串中一些字符并保持剩下的字符相对顺序不变的情况下得到的序列。如 "ace" 和 "abc" 都是 "abcde" 的子序列。数据范围:- 20% 的数据满足 , '?' 的总数量不超过 5 个,S 表示字符串 S 的长度,下同。- 50% 的数据满足 , '?' 的总数量不超过 5 个。- 100% 的数据满足 , ’?‘ 总数量无限制。
加载中...