Ибти пытался придумать историю, которая придала бы смысл этой задаче. Он решил вставить грустную историю.
Все были счастливы программировать, пока внезапно не случился перебой в электроснабжении, и лучший сайт спортивного программирования не вышел из строя. К счастью, системный администратор недавно купил новое оборудование, в том числе несколько ИБП. Таким образом, есть несколько серверов, которые всё ещё находятся в сети, но нам нужно, чтобы они все работали, чтобы раунд остался рейтинговым.
Представьте, что серверы представляют собой бинарную строку $$$s$$$ длины $$$n$$$. Если $$$i$$$-й сервер находится онлайн, то $$$s_i = 1$$$, иначе $$$s_i = 0$$$.
Системный администратор может выполнить следующую операцию под названием распределение электроэнергии, которая состоит из следующих этапов:
Мы называем бинарную строку $$$s$$$ длины $$$n$$$ рейтинговой, если мы можем включить все серверы (т.е. сделать $$$s_i = 1$$$ для $$$1 \le i \le n$$$) с помощью операции распределения электроэнергии произвольное количество раз (возможно, $$$0$$$). Ваша задача — найти количество рейтинговых строк длины $$$n$$$ по модулю $$$m$$$.
Первая и единственная строка содержится два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 5000$$$, $$$10 \le m \le 10^9$$$) — длина строки и требуемый модуль.
Выведите единственное целое число — количество рейтинговых бинарных строк длины $$$n$$$. Так как это число может быть большим, выведите его по модулю $$$m$$$.
2 100
1
3 10
2
4 3271890
4
17 123456
32347
В первом примере единственной рейтинговой строкой является 11. Таким образом, ответ $$$1$$$.
Во втором примере рейтинговыми строками являются:
В третьем примере рейтинговые строки:
Название |
---|