Задача . D. Лексихроматография

Пак Чанек любит свой факультет — факультет компьютерных наук Университета Индонезии (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\). В частности, пустая последовательность всегда лексикографически меньше любой непустой последовательности.