Задача . F. Большинство

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

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

Представьте, что серверы представляют собой бинарную строку \(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\).