Цветочные Часы находятся рядом с Зеркальным Озером много лет. Неспособные показывать время, они напоминают людям о его течении и о старых добрых днях.

На окружности Цветочных Часов находятся 2n цветков, пронумерованных от 1 до 2n по часовой стрелке, каждый цветок имеет один из возможных n цветов. Есть ровно два цветка каждого цвета, расстояние между которыми либо не больше, чем 2, либо равняется n. Кроме того, если цветки u и v имеют одинаковый цвет, то цветок, расположенный напротив u, и цветок, расположенный напротив v, тоже имеют одинаковый цвет: симметрия — это прекрасно!

Формально, расстояние между двумя цветками равно 1 плюс количество цветков на меньшей дуге между ними. Ниже показано возможная раскраска цветов при n = 6, которое описывает все возможные случаи.

Красотой раскраски называется произведение длин отрезков цветков, разделенных всеми цветами такими, что противоположный цветок имеет тот же цвет. Другими словами, чтобы вычислить красоту, нужно удалить из круга все цветки, которые имеют тот же цвет, что и цветок напротив них. Тогда красота равна произведению длин всех оставшихся отрезков. Обратите внимание, отрезки длины 0 тоже считаются. Если цветков, которые имеют тот же цвет, что и цветок напротив них, нет, то красота равна 0. Например, красота раскраски выше равна 1 × 3 × 1 × 3 = 9: отрезками являются {2}, {4, 5, 6}, {8} и {10, 11, 12}.

Возможно большое число различных раскрасок, удовлетворяющих всем ограничениям. Найдите сумму всех красот по всем возможным раскраскам по модулю 998 244 353. Две раскраски различны, если существует пара (u, v) (1 ≤ u, v ≤ 2n) такая, что цветы u и v имеют один цвет в одной из них, но не имеют один цвет в другой.