Bosco изучает поведение частиц. Он решил исследовать особенности поведения так называемой частицы «четыре-один-два». Он поступает следующим образом:
Имеется прямая длиной \(n+1\), где самая верхняя точка — позиция \(0\), а самая нижняя — позиция \(n+1\). Частица первоначально (в момент времени \(t=0\)) находится в позиции \(0\) и движется вниз. Частица движется со скоростью \(1\) единица в секунду. В позициях \(1,2,\ldots,n\) находятся \(n\) излучателей.
Каждый излучатель может быть описан бинарной строкой. Начальное состояние каждого излучателя — это первый символ его бинарной строки. Когда частица сталкивается с излучателем, она меняет направление своего движения, если текущее состояние излучателя равно \(\texttt{1}\), и продолжает двигаться в том же направлении, если его текущее состояние равно \(\texttt{0}\), и этот излучатель переходит в следующее состояние (следующее состояние для последнего состояния определяется как первое состояние). Кроме того, частица всегда меняет свое направление, если она находится в положении \(0\) или \(n+1\) в момент времени \(t > 0\).
Bosco хотел бы узнать длину цикла движения частицы. Длина цикла определяется как минимальное значение \(c\), такое, что для любого времени \(t \ge 0\) положение частицы в момент времени \(t\) совпадает с положением частицы в момент времени \(t+c\). Можно доказать, что такое значение \(c\) существует всегда. Поскольку он понимает, что ответ может быть слишком большим, он просит вас вывести ответ по модулю \(998244353\).
Примечание
В первом примере единственный излучатель на позиции \(1\) всегда имеет состояние \(\texttt{0}\). В моменты времени \(0,1,2,3\) позиции частицы равны \(0,1,2,1\) соответственно. Затем те же позиции будут повторяться, поэтому \(c=4\).
Анимация для второго примера: здесь или более плавная анимация.