You are given a string $S$ of length $n$. You need to partition it into several disjoint, non-empty, contiguous substrings $s_1, s_2, \dots, s_k$ ($k \ge 1$) such that:

• Each substring $s_i$ ($1 \le i \le k$) is non-periodic.
• Any two adjacent substrings are different, i.e., $s_i \neq s_{i+1}$ ($1 \le i < k$).
• The concatenation of $s_1, s_2, \dots, s_k$ from left to right is exactly the original string, i.e., $S = \overline{s_1s_2\dots s_k}$.

A string $S$ is periodic if and only if there exists an integer $k \ge 2$ and a string $s$ such that the concatenation of $k$ copies of $s$ equals $S$. For example, $S = \text{abab}$ is periodic because there exist $k=2$ and $s=\text{ab}$. A string is non-periodic if and only if it is not periodic. The strings $\text{ababa}$ and $\text{abcac}$ are non-periodic.

You need to calculate the number of different ways to partition the string. Since the number of ways can be very large, output the result modulo $998244353$. Two partition methods are considered different if the sequences of substrings are different.

Input

The input consists of a single line containing a string $S$ consisting only of lowercase letters.

Output

Output a single integer representing the number of ways modulo $998244353$.

Examples

Input 1

ababab

Output 1

22

Input 2

abracadabracadabracadabra

Output 2

16762880

Constraints

For all test cases, $|S| \le 200000$.

• Subtask 1 (7%): $|S| \le 300$.
• Subtask 2 (10%): $|S| \le 2000$.
• Subtask 3 (13%): $|S| \le 8000$.
• Subtask 4 (5%): Each character of $S$ is generated randomly from a specified character set.
• Subtask 5 (25%): It is guaranteed that for any substring of $S$, it is either non-periodic, or its periodicity (the $k$ described in the problem) does not exceed $10$.
• Subtask 6 (40%): No special constraints.