Рассмотрим некоторое множество различных символов \(A\) и некоторую строку \(S\), состоящую ровно из \(n\) символов, где каждый символ присутствует в \(A\).
Задан массив \(b\) из \(m\) целых чисел (\(b_1 < b_2 < \dots < b_m\)).
Разрешено проводить следующую операцию над строкой \(S\):
- Выбрать некоторый корректный \(i\) и выставить \(k = b_i\);
- Взять первые \(k\) символов \(S = Pr_k\);
- Взять последние \(k\) символов \(S = Su_k\);
- Заменить первые \(k\) символов \(S\) развернутой \(Su_k\);
- Заменить последние \(k\) символов \(S\) развернутой \(Pr_k\).
Например, рассмотрим строку \(S =\) «abcdefghi» и \(k = 2\). \(Pr_2 =\) «ab», \(Su_2 =\) «hi». Развернутые \(Pr_2 =\) «ba», \(Su_2 =\) «ih». Следовательно, полученная \(S\) равна «ihcdefgba».
Данная операция может быть проведена произвольное количество раз (возможно, ноль). Любой \(i\) может быть выбран несколько раз в ходе проведения операций.
Назовем строки \(S\) и \(T\) равными тогда и только тогда, когда существует такая последовательность операций, которая преобразовывает строку \(S\) в строку \(T\). Для приведенного выше примера «abcdefghi» и «ihcdefgba» равны. Обратите внимание, что это подразумевает и \(S = S\).
Задача проста. Посчитайте количество различных строк.
Ответ может быть достаточно велик, поэтому посчитайте его по модулю \(998244353\).