Доктор Селим Джунц из Межзвездного Космоаналитического Бюро вот уже как одиннадцать месяцев находился на Сарке. Он прибыл сюда, чтобы расследовать исчезновение своего коллеги, и обратился к саркитским властям, однако все поиски не давали никаких результатов. Тогда Селим начал подозревать: а вдруг от него что-то скрывают?
Селим много лет работал с Риком, и поэтому уверен, что тот не мог отступиться от своей идеи и улететь далеко. Остается два варианта — либо он сел на какой-либо другой планете в ближайшем пространстве, либо его силой удерживают на Сарке. Найти друга в одиночку на целой планете, а может и двух, не представлялось возможным, поэтому Селим решил начать поиски с обнаружения энергетического спектра корабля Рика.
Благодаря современным технологиям и качественному оборудованию Селим через несколько часов уже имел результат анализа, закодированный строкой $s$ из символов латинского алфавита. Однако программного обеспечения, чтобы его расшифровать, у Селима не было, а людям с Сарка он не доверяет, поэтому он просит вас определить результат. Результатом анализа является число подпоследовательностей этой строки вида $f_i$ для какого-либо $1 <= i <= 26$:
В единственной строке задана строка $s$ $(1 <= | s | <= 5000)$.
Выведите число подпоследовательностей этой строки вида $f_i$ по модулю $998244353$.
Из строки "$a b a c a b a$" можно выбрать $4$ подпоследовательности $f_1 =$ "$a$", $6$ подпоследовательностей $f_2 =$ "$a b a$" и одну подпоследовательность $f_3 =$ "$a b a c a b a$".
Строка "$b$" не содержит искомых подпоследовательностей.
## Входные Данные
В единственной строке задана строка $s$ $(1 <= | s | <= 5000)$.
## Выходные Данные
Выведите число подпоследовательностей этой строки вида $f_i$ по модулю $998244353$.
## Примеры
Входные данныеabacaba
Выходные данные11
Входные данныеb
Выходные данные0
## Примечание
Из строки "$a b a c a b a$" можно выбрать $4$ подпоследовательности $f_1 =$ "$a$", $6$ подпоследовательностей $f_2 =$ "$a b a$" и одну подпоследовательность $f_3 =$ "$a b a c a b a$".Строка "$b$" не содержит искомых подпоследовательностей.
[samples]
**Definitions**
Let $ N \in \mathbb{Z} $ be the number of rectangular boxes.
For each box $ i \in \{1, \dots, N\} $, let $ w_i, h_i \in \mathbb{Z}^+ $ denote its width and height.
Each box can be placed unrotated ($ w_i \times h_i $) or rotated ($ h_i \times w_i $), so its effective width and height are chosen from $ \{(w_i, h_i), (h_i, w_i)\} $.
Let $ B = (b_1, b_2, \dots, b_N) $ be a sequence of boxes placed in a row along the $ x $-axis, where each $ b_i = (w_i', h_i') $ is the chosen orientation of box $ i $, with $ w_i' \in \{w_i, h_i\} $, $ h_i' \in \{h_i, w_i\} $, and $ w_i' \cdot h_i' = w_i \cdot h_i $.
The boxes are placed contiguously: the total width is $ \sum_{i=1}^N w_i' $, and box $ i $ occupies the horizontal interval $ \left[ \sum_{j=1}^{i-1} w_j', \sum_{j=1}^{i} w_j' \right] \times [0, h_i'] $.
**Constraints**
1. $ 3 \leq N \leq 250000 $
2. $ 1 \leq w_i, h_i \leq 10^6 $ for all $ i \in \{1, \dots, N\} $
3. Boxes must be placed in a single row with no gaps.
4. Water can be retained at height $ y $ if, for some $ x $, the point $ (x, y) $ is not inside any box, and there exist boxes to the left and right of $ x $ whose top edges are at height $ \geq y $.
**Objective**
Maximize the total area of water that can be stored:
$$
\max_{B} \int_{x=0}^{\sum w_i'} \left( \min\left( \max_{j: x_j^{\text{left}} \leq x} h_j', \max_{j: x_j^{\text{right}} \geq x} h_j' \right) \right) dx - \sum_{i=1}^N w_i' h_i'
$$
where the integral computes the area under the "ceiling" formed by the left and right maximum heights at each $ x $, and the subtraction removes the volume occupied by the boxes.
Equivalently, define the water area as:
$$
\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \left( \min(h_i', h_j') \cdot \left( \sum_{k=i+1}^{j-1} w_k' \right) \right) \cdot \mathbf{1}_{\text{no box } k \in (i,j) \text{ has } h_k' > \min(h_i', h_j')}
$$
but since water flows freely left/right and is constrained only by the *highest* box to the left and right, the correct formulation is:
Let $ H_i = h_i' $ be the height of box $ i $ in chosen orientation.
Water stored above the boxes is bounded by the "container" formed by the left and right maxima:
For a fixed arrangement $ B $, the water area is:
$$
\sum_{i=1}^N \sum_{j=i+1}^N \left( \min(H_i, H_j) \cdot \left( \sum_{k=i+1}^{j-1} w_k' \right) - \sum_{k=i+1}^{j-1} w_k' H_k \right) \cdot \mathbf{1}_{\forall k \in (i,j), H_k \leq \min(H_i, H_j)}
$$
But since water flows and fills to the level of the *minimum of the leftmost and rightmost barrier*, and only if all intermediate boxes are lower, the **maximum water area** achievable is:
$$
\max_{\text{permutation } \pi, \text{ orientations}} \sum_{1 \leq i < j \leq N} \left( \min(H_{\pi(i)}, H_{\pi(j)}) \cdot \left( \sum_{k=i+1}^{j-1} w_{\pi(k)}' \right) \right) \quad \text{where } H_{\pi(k)} \leq \min(H_{\pi(i)}, H_{\pi(j)}) \text{ for all } k \in (i,j)
$$
This is equivalent to the **maximum area of a histogram container** with variable-width bars and selectable heights (from two options per bar), where water is trapped between two bars if all intermediate bars are not taller than the shorter of the two.
Thus, the problem reduces to:
**Objective (Final Formalization)**
Choose for each box $ i $ an orientation $ (w_i', h_i') \in \{(w_i, h_i), (h_i, w_i)\} $, and a permutation $ \pi \in S_N $, to maximize:
$$
\max_{\pi, \{w_i', h_i'\}} \sum_{1 \leq i < j \leq N} \min(h_{\pi(i)}', h_{\pi(j)}') \cdot \left( \sum_{k=i+1}^{j-1} w_{\pi(k)}' \right) \cdot \mathbf{1}_{\forall k \in \{i+1,\dots,j-1\}, h_{\pi(k)}' \leq \min(h_{\pi(i)}', h_{\pi(j)}')}
$$