题目描述

给定一个由字符 a、b、c 组成的字符串 $S$。

求 $S$ 中满足任意两个相邻字符都不相同的非空子序列的数量，结果对 $998244353$ 取模。

即使两个子序列作为字符串是相同的，只要它们来自 $S$ 中的不同位置，就被视为不同的子序列。

什么是子序列？ $S$ 的子序列是从 $S$ 中删去零个或多个字符后，将剩余字符按原顺序拼接得到的字符串。例如，ab、ac 是 abc 的子序列，但 ca、bb 不是 abc 的子序列。

输入格式

输入只有一行，一个字符串 $S$。

输出格式

输出一行，表示满足条件的子序列数量对 $998244353$ 取模的结果。

abbc

11

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

378217423

数据范围与提示

样例 1 解释： 满足条件的子序列共 $11$ 个：

• a（第 $1$ 个字符）
• b（第 $2$ 个字符）
• b（第 $3$ 个字符）
• c（第 $4$ 个字符）
• ab（第 $1,2$ 个字符）
• ab（第 $1,3$ 个字符）
• ac（第 $1,4$ 个字符）
• bc（第 $2,4$ 个字符）
• bc（第 $3,4$ 个字符）
• abc（第 $1,2,4$ 个字符）
• abc（第 $1,3,4$ 个字符）

注意：第 $2$ 和第 $3$ 个子序列内容相同但位置不同，视为不同子序列。

样例 2 解释： 输出答案对 $998244353$ 取模的结果。

对于 $100\%$ 的数据，$S$ 是长度在 $1$ 到 $3 \times 10^5$ 之间的由 a、b、c 组成的字符串。