题目描述

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

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

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

什么是子串？ $S$ 的子串是从 $S$ 的开头删去零个或多个字符、从末尾删去零个或多个字符后得到的字符串。例如，ab 是 abc 的子串，但 ac 不是 abc 的子串。

输入格式

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

输出格式

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

abbc

6

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

760

数据范围与提示

样例 1 解释： 满足条件的子串共 6 个：

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

注意：第 $2$ 和第 $3$ 个子串虽然字符串内容相同，但位置不同，视为不同子串。

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