H. Homogeneous Mixings
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In your current experiments for the Imminently Collapsing Physics Congregation, you are studying the 26 Dark Matter elements. You already found a way to organize a group of their particles in a chain, but unfortunately that sometimes results in the collapse of the whole structure.

Your current theory is that your method is shuffling the particles around randomly, and that the collapse happens if any two particles of the same element are next to each other. To test that theory, you would like to know what is the expected probability of such a collapse, if the theory is correct. That is, out of all possible permutations of the set of particles you're using in your experiment, you would like to know the probability of a uniformly randomly picked permutation to have at least one pair of particles of the same element adjacent to each other.

For example, if you have particles aabbbc, there are 720 possible permutations, with 60 distinct ones if you factor out the order of equal particles. Out of those, only 10 don't cause a collapse:

  1. ababcb
  2. abcbab
  3. bababc
  4. babacb
  5. babcab
  6. babcba
  7. bacbab
  8. bcabab
  9. bcbaba
  10. cbabab
Input

Input contains a single string $$$S$$$ representing the particles involved in the experiment, $$$1 \leq |S| \le 10^5$$$. Each character of the string is a lowercase letter representing the element of a particle. They are organized in alphabetic order.

Output

Print one integer — the probability of collapse, taken modulo $$$998244353$$$. The required expected probability can be represented as an irreducible fraction $$$\frac{p}{q}$$$. You have to print the value $$$p \cdot q^{-1} \mod 998244353$$$.

Examples
Input
aabbbc
Output
831870295
Input
aaab
Output
1
Input
abcdefghijklmnopqrstuvwxyz
Output
0