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$$$.