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

Все были счастливы программировать, пока внезапно не случился перебой в электроснабжении, и лучший сайт спортивного программирования не вышел из строя. К счастью, системный администратор недавно купил новое оборудование, в том числе несколько ИБП. Таким образом, есть несколько серверов, которые всё ещё находятся в сети, но нам нужно, чтобы они все работали, чтобы раунд остался рейтинговым.

Представьте, что серверы представляют собой бинарную строку $$$s$$$ длины $$$n$$$. Если $$$i$$$-й сервер находится онлайн, то $$$s_i = 1$$$, иначе $$$s_i = 0$$$.

Системный администратор может выполнить следующую операцию под названием распределение электроэнергии, которая состоит из следующих этапов:

• Выберите два сервера в позициях $$$1 \le i < j \le n$$$ так, чтобы оба были подключены к сети (т. е. $$$s_i=s_j=1$$$). Распределение начинается только с онлайн-серверов.
• Проверьте, достаточно ли мощности для распространения. Мы считаем, что мощности достаточно, если количество включенных серверов в диапазоне $$$[i, j]$$$ не меньше количества выключенных серверов в диапазоне $$$[i, j]$$$. Более формально, проверьте, что $$$2 \cdot (s_i + s_{i+1} + \ldots + s_j) \ge j - i + 1$$$.
• Если условие выше выполнено, включите все серверы в оффлайне в диапазоне $$$[i, j]$$$. Более формально, присвоить $$$s_k := 1$$$ для всех $$$k$$$ от $$$i$$$ до $$$j$$$.

Мы называем бинарную строку $$$s$$$ длины $$$n$$$ рейтинговой, если мы можем включить все серверы (т.е. сделать $$$s_i = 1$$$ для $$$1 \le i \le n$$$) с помощью операции распределения электроэнергии произвольное количество раз (возможно, $$$0$$$). Ваша задача — найти количество рейтинговых строк длины $$$n$$$ по модулю $$$m$$$.