Алиса и Боб собираются сыграть в игру. У них есть $$$n$$$ раскрашенных полосок бумаги; $$$i$$$-я полоска поделена на $$$a_i$$$ клеток, пронумерованных от $$$1$$$ до $$$a_i$$$. Каждая клетка может быть раскрашена в один из $$$3$$$ цветов.

В самом начале игры Алиса и Боб ставят на полоски $$$n$$$ фишек, $$$i$$$-я фишка ставится в клетку $$$a_i$$$ полоски $$$i$$$. Затем игроки совершают ходы по очереди, Алиса ходит первой. В процессе хода игрок должен выбрать ровно одну фишку и подвинуть ее на $$$1$$$, $$$2$$$ или $$$3$$$ клетки к началу полоски (если текущая клетка имеет номер $$$x$$$, то можно подвинуть фишку в клетку $$$x - 1$$$, $$$x - 2$$$ или $$$x - 3$$$). Есть два ограничения: фишка не может покидать пределы полоски (например, если фишка находится в ячейке $$$3$$$, нельзя подвинуть ее на $$$3$$$ ячейки); и некоторые ходы могут быть недоступны из-за цвета текущей клетки (эти запреты обозначаются матрицей $$$f$$$ размера $$$3 \times 3$$$, где $$$f_{i, j} = 1$$$, если можно подвинуть фишку на $$$j$$$ клеток к началу полоски из клетки с цветом $$$i$$$, или $$$f_{i, j} = 0$$$, если этот ход недоступен). Игрок, который не может сделать ход, проигрывает.

Изначально некоторые клетки могут быть бесцветными. Боб может покрасить все бесцветные клетки так, как он хочет (но нельзя оставлять бесцветную клетку бесцветной). Назовем раскраску хорошей, если Боб может выиграть игру при любых действиях Алисы, если клетки окрашены в соответствии с этой раскраской. Две раскраски считаются различными, если существует хотя бы одна клетка, которая в этих раскрасках имеет разные цвета.

Боб хочет посчитать количество хороших раскрасок. Можете ли вы сделать это для него?

Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.