Вам дано \(n\) домино. Каждое домино имеет левую и правую клетку. Каждая клетка может быть окрашена в черный или белый цвет. Некоторые клетки уже окрашены, а некоторые еще нет.
Раскраска считается допустимой тогда и только тогда, когда можно переставить доминошки в некотором порядке так, чтобы для каждого \(1 \le i \le n\) цвет правой клетки \(i\)-го домино отличался от цвета левой клетки \(((i \bmod n)+1)\)-го домино.
Обратите внимание, что домино нельзя вращать, поэтому левая клетка всегда остается левой, а правая — правой.
Подсчитайте количество допустимых способов раскрасить еще не раскрашенные клетки домино. Два способа считаются разными, если есть клетка, которая в одном способе окрашивается в белый цвет, а во втором — в черный. В частности, раскраски BW WB и WB BW различны (и обе недопустимы).
Поскольку это число может быть очень большим, выведите его по модулю \(998\,244\,353\).
Примечание
В первом примере есть только одна доминошка, и нам нужно, чтобы цвет ее правой клетки отличался от цвета ее левой клетки. Этого можно добиться только одним способом.
Во втором примере существует только \(2\) таких раскраски:
BB WW и WB WB.