You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

请注意本题的空间限制。

小 Y 对字符串很感兴趣，他定义一个长度为 $n$ 的字符串 $S$ （下标为 $0,1,\dots,n-1$）是循环的，当且仅当符合以下条件：

• 字符串 $S$ 的长度大于 $1$ ，即 $n>1$，并且

• 存在某个正整数 $k\in [1,n)$，满足 $k$ 是 $n$ 的约数，并且对于任意的 $i\in [0,n)$ 都有 $S_i=S_{i\mod k}$

这里 $S_i$ 表示字符串 $S$ 中下标为 $i$ 的字符。

小 Z 也对字符串很感兴趣，他定义一个长度为 $n$ 的字符串 $S$ 的划分为数列 $\{p_1, p_2, \cdots , p_k\} (k \ge 2)$，满足 $p_1=0,p_k=n$，且对于任意 $i\in [2,k]$ 都有 $p_i>p_{i-1}$。这样可以看作把字符串 $S$ 划分成了若干段，每一段的形式为第 $p_i$ 个字符到第 $p_{i+1}-1$ 个字符。两个分割不同，当且仅当对应的数列不同。

小 Y 和小 Z 一拍即合，定义了不循环分割。称一个分割是不循环分割，当且仅当分割中的每一段都不是循环的。现在他俩想知道，给定字符串 $S$，有多少种不同的不循环分割？答案对 $998244353$ 取模。

输入格式

从 partition.in 文件读入数据。

一行一个小写字母构成的字符串 $S$ 。

输出格式

输出到 partition.out 文件。

输出一个整数，代表答案，对 $998244353$ 取模。

样例 1

aab

3

对于样例 1，三种可能的划分是：

1. {0, 1, 2, 3} , 被分成了’a’ + ’a’ + ’b’ 。
2. {0, 1, 3} , 被分成了 ’a’ + ’ab’ 。
3. {0, 3} , 整串保留，作为一种划分。

样例 2

点击链接 ex_partition2.in 和 ex_partition2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于每个测试点， 字符串 $S$ 的长度不超过 $5\times 10^3$。