Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам необходимо найти количество хороших массивов. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Кевин посещает Красную Церковь и нашел загадку на стене.
Пусть для массива \( a \) величина \( c(l,r) \) обозначает количество различных чисел среди \( a_l, a_{l+1}, \ldots, a_r \). В частности, если \( l > r \), \( c(l,r) = 0 \).
Вам дана строка \( s \) длиной \( n \), содержащая только \( \texttt{L} \) и \( \texttt{R} \). Назовем неотрицательный массив \( a \) хорошим, если для всех \( 1 \leq i \leq n \) выполняются следующие условия:
- если \(s_i=\verb!L!\), то \(c(1,i-1)=a_i\);
- если \(s_i=\verb!R!\), то \(c(i+1,n)=a_i\).
Вам нужно найти количество хороших массивов \(a\). Поскольку ответ может быть большим, вам нужно вывести ответ по модулю \(998\,244\,353\).