C. Посчитайте бинарные строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано целое число $$$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$$$.

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

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 100$$$).

Затем следуют $$$n$$$ строк. В $$$i$$$-й из них задано $$$n-i+1$$$ целых чисел $$$a_{i,i}, a_{i,i+1}, a_{i,i+2}, \dots, a_{i,n}$$$ ($$$0 \le a_{i,j} \le 2$$$).

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

Выведите одно целое число — количество строк, удовлетворяющих ограничениям задачи, взятое по модулю $$$998244353$$$.

Примеры
Входные данные
3
1 0 2
1 0
1
Выходные данные
6
Входные данные
3
1 1 2
1 0
1
Выходные данные
2
Входные данные
3
1 2 1
1 0
1
Выходные данные
0
Входные данные
3
2 0 2
0 1
1
Выходные данные
0
Примечание

В первом примере ограничениям соответствуют строки 001, 010, 011, 100, 101, 110.

Во втором примере ограничениям соответствуют строки 001, 110.