题目描述

给定一个只包含字母 a、b、c 的字符串 $S$。

请你计算 $S$ 的非空子序列中，相邻字符均不相同的子序列个数，并将答案对 $998244353$ 取模。

输入格式

第一行输入一个字符串 $S$

输出格式

输出符合条件的子序列数量。

abbc

11

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

378217423

提示

样例解释 1

所有符合条件的子序列有以下 $11$ 个：

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

需要注意的是，正如第 $2$ 个和第 $3$ 个子序列一样，若取自不同位置，即使内容相同，也视为不同的子序列。

数据范围

保证给定的字符串只包含 a、b、c。

• 对于 $20\%$ 的数据满足：$|S|\le 15$。
• 对于 $50\%$ 的数据满足：$|S|\le 5000$。
• 对于 $100\%$ 的数据满足：$|S|\le 3\times 10^5$。