Cycle Binary String Swapping

You are given a binary string \(a_0a_1a_2\dots a_{n-1}\) arranged on a cycle. Each second, every occurrence of the substring 01 is changed simultaneously to 10. In other words, for every index \(i\) (with indices taken modulo \(n\)), if \(a_i = 0\) and \(a_{(i+1) \bmod n} = 1\), then the bits at positions \(i\) and \(i+1\) are swapped.

You need to determine how many different binary strings will occur as time tends to infinity, and output this number modulo \(998244353\). Note that two strings \(a_0a_1\dots a_{n-1}\) and \(b_0b_1\dots b_{n-1}\) are considered different if there exists an index \(i\) such that \(a_i \neq b_i\). This means that even cyclic shifts of a string are considered different if they are not identical element-wise.

Observation: Let \(n\) be the length of the string and let \(k\) be the number of ones in the string. It can be shown that the only states that the process can cycle through have a count equal to \(\frac{n}{\gcd(n,k)}\) (using the fact that \(\gcd(n,0)=n\) and \(\gcd(n,n)=n\), which gives \(1\) when the string is all zeros or all ones). Therefore, the answer is given by:

[ \text{answer} = \frac{n}{\gcd(n,k)} \mod 998244353. ]

inputFormat

The input consists of a single line containing a binary string. The length \(n\) of the string satisfies \(1 \le n\). The string represents the cycle \(a_0a_1\dots a_{n-1}\).

outputFormat

Output a single integer, which is the number of different strings that will occur in the process (over an infinite number of seconds), taken modulo \(998244353\).

sample

10

2