题目描述

CauchySheep 有一个字符串 $s$。他把 $s$ 的所有不同非空子串都拿出来，每个不同子串看作有向图中的一个点。

对于两个子串 $a,b$，若满足：

• $|b|+1=|a|$；
• $b$ 是 $a$ 的一个子串；

则从点 $a$ 向点 $b$ 连一条有向边。

请你计算在这张有向图中，从点 $s$ 出发的简单路径数量，并输出它对 $998244353$ 取模后的结果。

简单路径指路径上不重复经过同一个点。长度为 $0$、只包含起点 $s$ 的路径也计入答案。

以字符串 abba 为例，图中点包括 abba、abb、bba、bb、ab、ba、b、a 等不同非空子串，并用有向边表示“删去一个字符长度后仍为子串”的关系。该图用于说明样例 1 的子串有向图结构。

输入格式

输入一行一个字符串 $s$，由小写英文字母组成。

输出格式

输出一行一个整数，表示从 $s$ 出发的简单路径数量对 $998244353$ 取模后的结果。

数据范围

• $1\le |s|\le 300000$。

样例 1

输入

abba

输出

13

样例 2

输入

benbeipo

输出

255

样例 3

输入

iqiiiiiiqq

输出

300

样例 4

输入

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

输出

35