Задано целое число \(n\) и последовательность \(a\) из \(n-1\) целых чисел: каждый элемент равен либо \(0\), либо \(1\).
Требуется построить такую строку длины \(n\), что:
- каждая буква — одна из «abcd»;
- если \(a_i=1\), то \(i\)-й суффикс строки лексикографически меньше \((i+1)\)-го суффикса;
- если \(a_i=0\), то \(i\)-й суффикс строки лексикографически больше \((i+1)\)-го суффикса.
Будут заданы \(q\) запросов вида:
- \(i\) (\(1 \le i \le n - 1\)) — сменить значение \(a_i\) на противоположное (если \(a_i=0\), то установить \(a_i\) в \(1\), и наоборот).
После каждого запроса выведите количество различных строк, удовлетворяющих данным ограничениям, по модулю \(998\,244\,353\).
Выходные данные
После каждого запроса выведите количество различных строк, удовлетворяющих данным ограничениям, по модулю \(998\,244\,353\).
Примечание
\(i\)-й суффикс строки — это последовательная подстрока, которая начинается в \(i\)-й позиции и заканчивается в последней позиции.
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Две строки \(a\) и \(b\) длины \(n\) различаются, если существует такая позиция \(i\), что \(a_i \neq b_i\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
0
1
1
|
6
10
|
|
2
|
3 4
0 0
1
2
1
2
|
20
10
14
20
|
|
3
|
10 10
0 0 0 1 1 1 0 1 0
4
1
8
4
2
9
5
6
6
8
|
1815
3201
2710
2776
2290
1644
2668
1271
2668
2436
|