Jovsi 依然是一个强壮的男孩。他从小就喜欢机关枪，也经常模仿它们，但出于某种原因，他喊的不是 trtrtrt 或 bambambam，而是 acacacacac。

Malnar 先生对 Jovsi 的力量并不感兴趣，他只关心 Jovsi 解决问题的能力。于是有一天，他送给 Jovsi 一根棍子，上面从左到右写着 $n$ 个字母。Malnar 先生认为对称的棍子非常漂亮，因此他特别关注回文对。回文对是指有序自然数对 $(l, r)$，其中 $1 \le l \le r \le n$，且从第 $l$ 个位置到第 $r$ 个位置的子串是一个回文串。回文串是指从左向右读和从右向左读都相同的字符串。

随后，Malnar 先生决定给 Jovsi 出一个挑战。挑战由一个自然数 $k$ 以及 $k$ 个回文对 $(l_i, r_i)$ 组成，这些回文对满足 $l_1 < l_2 < \dots < l_k$ 且 $r_1 > r_2 > \dots > r_k$。

Jovsi 必须为各种情况做好准备，因此他想知道 Malnar 先生可能会给他出多少种不同的挑战。请帮助 Jovsi 计算不同挑战的总数，结果对 $998244353$ 取模。

输入格式

输入仅一行，包含一个由小写英文字母组成的字符串，表示写在 Malnar 先生棍子上的字母序列。字符串长度不超过一百万。

输出格式

输出一行，表示不同挑战的总数对 $998244353$ 取模后的结果。

样例

输入 1

anadanaokoabanana

输出 1

65

输入 2

acacacacac

输出 2

242

输入 3

ananas

输出 3

18