Пак Чанек любит свой факультет — факультет компьютерных наук Университета Индонезии (Fasilkom). Он хочет поиграть с цветами эмблемы факультета - синим и красным.

Имеется массив $$$a$$$, состоящий из $$$n$$$ элементов, элемент $$$i$$$ имеет значение $$$a_i$$$. Пак Чанек хочет окрасить каждый элемент массива в синий или красный цвет так, чтобы выполнялись следующие условия:

• Если все синие элементы складываются в подпоследовательность$$$^\dagger$$$ и все красные элементы тоже, то синяя подпоследовательность строго меньше красной подпоследовательности лексикографически$$$^\ddagger$$$.
• Массив $$$a$$$ не имеет ни одного несбалансированного подмассива. Подмассив называется несбалансированным тогда и только тогда, когда существует такое значение $$$k$$$, что количество красных элементов на этом подмассиве со значением $$$k$$$ и количество синих элементов со значением $$$k$$$ отличается хотя бы на $$$2$$$.
• Заметим, что можно покрасить все элементы массива в один и тот же цвет.

Сколько различных раскрасок удовлетворяют всем этим условиям? Поскольку ответ может быть очень большим, выведите ответ по модулю $$$998\,244\,353$$$. Две раскраски различны тогда и только тогда, когда существует хотя бы один элемент, который в одной раскраске является синим, а в другой - красным.

$$$^\dagger$$$ Подпоследовательность массива - это последовательность, которая может быть получена из массива путем удаления некоторых элементов (возможно, ни одного), без изменения порядка оставшихся элементов.

$$$^\ddagger$$$ Пусть $$$p$$$ и $$$q$$$ - две различные последовательности. Считается, что последовательность $$$p$$$ лексикографически меньше последовательности $$$q$$$ тогда и только тогда, когда $$$p$$$ является префиксом $$$q$$$ или существует индекс $$$i$$$ такой, что $$$p_j=q_j$$$ для всех $$$1\leq j<i$$$, и $$$p_i<q_i$$$. В частности, пустая последовательность всегда лексикографически меньше любой непустой последовательности.