#P18835. [Croatian CPC2019] Jaki Jovsi

[Croatian CPC2019] Jaki Jovsi

[Croatian CPC2019] Jaki Jovsi

题目描述

给定一个长度为 nn 的小写英文字母字符串 ss,字符位置从 11 开始编号。

如果子串 slsl+1⋯srs_l s_{l+1}\cdots s_r 是回文串,则称有序对 (l,r)(l,r) 为一个回文区间,其中 1≤l≤r≤n1\le l\le r\le n。回文串是正着读和反着读都相同的字符串。

一个挑战由一个正整数 kk 和 kk 个回文区间 (l1,r1),…,(lk,rk)(l_1,r_1),\ldots,(l_k,r_k) 组成,并且满足

l1<l2<⋯<lk,r1>r2>⋯>rk.l_1<l_2<\cdots<l_k,\qquad r_1>r_2>\cdots>r_k.

也就是说,每个后续区间都严格位于前一个区间的内部,左右端点都必须向内移动。

求不同挑战的总数,对 998244353998244353 取模。区间的位置属于挑战的一部分;如果 kk 不同,或某个位置上的区间不同,则视为不同挑战。

输入格式

输入一行一个非空字符串 ss,仅由小写英文字母组成,长度不超过 10610^6。

输出格式

输出一个整数,表示不同挑战数量对 998244353998244353 取模的结果。

样例 1

输入

anadanaokoabanana

输出

65

样例 2

输入

acacacacac

输出

242

样例 3

输入

ananas

输出

18