Вам дано $$$n$$$ домино. Каждое домино имеет левую и правую клетку. Каждая клетка может быть окрашена в черный или белый цвет. Некоторые клетки уже окрашены, а некоторые еще нет.

Раскраска считается допустимой тогда и только тогда, когда можно переставить доминошки в некотором порядке так, чтобы для каждого $$$1 \le i \le n$$$ цвет правой клетки $$$i$$$-го домино отличался от цвета левой клетки $$$((i \bmod n)+1)$$$-го домино.

Обратите внимание, что домино нельзя вращать, поэтому левая клетка всегда остается левой, а правая — правой.

Подсчитайте количество допустимых способов раскрасить еще не раскрашенные клетки домино. Два способа считаются разными, если есть клетка, которая в одном способе окрашивается в белый цвет, а во втором — в черный. В частности, раскраски BW WB и WB BW различны (и обе недопустимы).

Поскольку это число может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.