I2. Кевин и загадка (сложная версия)
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам необходимо найти количество хороших массивов. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Кевин посещает Красную Церковь и нашел загадку на стене.

Пусть для массива $$$ 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$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t \le 10^4$$$) — количество наборов. Далее следует описание наборов.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — длина строки $$$s$$$.

Вторая строка каждого набора содержит строку $$$s$$$ длиной $$$n$$$, содержащую только латинские заглавные буквы $$$\verb!L!$$$ и $$$\verb!R!$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите количество хороших массивов по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
3
LLR
3
RRL
4
RRLR
5
LLRLR
Выходные данные
1
2
0
1
Примечание

Все массивы, удовлетворяющие условиям, можно найти в простой версии этой задачи.