I-Indivisible Partition_2023年第六届广西大学生程序设计竞赛（正式赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

Eva defines a string $S$ with length $n$ (indexed from $0$ to $n-1$ ) is divisible if:

the length of $S$ is greater than $1$ (i.e. $n>1$ ) , and
there exists a positive integer $k\in [1,n)$ satisfying $k|n$ (i.e. $k$ is a divisor of $n$ ) , and for all integer $i\in [0, n)$ , $S_i=S_{i\ \text{mod}\ k}$

Here $S_i$ denotes the character of $S$ with index $i$ , for example, let $S=$ abcde then $S_0=$ a and $S_1=$ b.
Then, Eva defines a string $S$ is indivisible if $S$ is not divisible.
For example, string abcde or string a is indivisible, but string aa is not indivisible.

Colin defines an indivisible partition of a string $S$ with length $n$ as a series of integers $\{p_1,p_2,\dots,p_k\}\ (k \ge 2)$ satisfying:

$p_1=0,\ p_k=n$ , and
for all integer $i\in [2, k]$ satisfying $p_i>p_{i-1}$ and $S[p_{i-1}:p_i-1]$ is indivisible.

Here $S[l:r]$ denotes the substring of $S$ with index form $l$ to $r$ , for example, let $S=$ abcde then $S[1:3]=$ bcd .

Given a string $S$ , please count the number of different indivisible partitions of $S$ module 998244353.

We consider two indivisible partitions $\{p_1,p_2,\dots,p_{k_1}\},\{p_1',p_2',\dots,p_{k_2}'\}$ are different if $k_1\not =k_2$ , or there exists an integer $i\in[1, k_1]$ satisfies $p_i\not = p_i'$ .

Please note the unusual memory limit.

输入描述:

The first line contains a string  consisting of lowercase letters, representing the given string.

输出描述:

A single integer, represents the number of different indivisible partitions of string  module 998244353.

示例1

输入

复制

aab

输出

复制

说明

the 3 different indivisible partitions of aab are:

1.  , the string is divided into a + a + b
2.  , the string is divided into a + ab
3.  , the string aab itself meets the definition of indivisible.