Дано целое число \(n\). Вы должны посчитать количество бинарных (состоящих из символов 0 и/или 1) строк \(s\), удовлетворяющих следующим условиям.
Для каждой пары целых чисел \((i, j)\), в которой \(1 \le i \le j \le n\), дано целое число \(a_{i,j}\). Оно соответствует следующему ограничению на строку \(s_i s_{i+1} s_{i+2} \dots s_j\):
- если \(a_{i,j} = 1\), все символы в строке \(s_i s_{i+1} s_{i+2} \dots s_j\) должны быть одинаковыми;
- если \(a_{i,j} = 2\), в подстроке \(s_i s_{i+1} s_{i+2} \dots s_j\) должна быть хотя бы одна пара различных символов;
- если \(a_{i,j} = 0\), на подстроку \(s_i s_{i+1} s_{i+2} \dots s_j\) нет ограничений.
Посчитайте количество бинарных строк \(s\) длины \(n\), удовлетворяющих данным условиям. Так как ответ может быть очень большим, выведите его по модулю \(998244353\).
Выходные данные
Выведите одно целое число — количество строк, удовлетворяющих ограничениям задачи, взятое по модулю \(998244353\).
Примечание
В первом примере ограничениям соответствуют строки 001, 010, 011, 100, 101, 110.
Во втором примере ограничениям соответствуют строки 001, 110.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 0 2
1 0
1
|
6
|
|
2
|
3
1 1 2
1 0
1
|
2
|
|
3
|
3
1 2 1
1 0
1
|
0
|
|
4
|
3
2 0 2
0 1
1
|
0
|