问题描述

一个DDoS类型的字符串是一个长度为4的字符串，由大写字母和小写字母组成，满足以下两个条件：

• 第一个、第二个和第四个字符是大写字母，第三个字符是小写字母。
• 第一个和第二个字符相等。

例如，DDoS和AAaA都是DDoS类型的字符串，而ddos和IPoE则不是。

给定一个由大写字母、小写字母和?组成的字符串S。设S中出现?的次数为q。可以通过使用大写或小写英文字母替换S中的每个?，从而获得$52^q$个字符串。在这些字符串中，找出那些不包含DDoS类型字符串作为子序列的字符串的数量，取模$998244353$。

注意事项

一个字符串的子序列是通过从字符串中删除零个或多个字符并连接剩下的字符而得到的字符串。例如，AC是ABC的一个子序列，而RE不是ECR的子序列。

约束条件

• S由大写字母、小写字母和?组成。
• S的长度介于4到3×10^5之间，包括边界值。

输入

输入数据从标准输入读入，输入格式如下：

S

输出

打印输出答案。

示例输入1

DD??S

示例输出1

676

当至少有一个?被替换为小写字母时，所得到的字符串将包含DDoS类型字符串作为子序列。

示例输入2

????????????????????????????????????????

示例输出2

858572093

计算模$998244353$的计数。

示例输入3

?D??S

示例输出3

136604