D1. Верхняя ячейка (упрощенная версия)
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта версия задачи отличается от следующей только ограничением на $$$n$$$.

Обратите внимание, что ограничение по памяти в этой задаче ниже, чем в других.

У вас есть вертикальная полоска из $$$n$$$ ячеек, последовательно пронумерованных сверху вниз от $$$1$$$ до $$$n$$$.

У вас также есть токен, изначально расположенный в ячейке $$$n$$$. Вы будете двигать токен вверх до тех пор, пока он не окажется в ячейке $$$1$$$.

Пусть в некоторый момент токен находится в ячейке $$$x > 1$$$. Один сдвиг токена может иметь любой из следующих двух видов:

  • Вычитание: вы выбираете целое число $$$y$$$ от $$$1$$$ до $$$x-1$$$ включительно и перемещаете токен из ячейки $$$x$$$ в ячейку $$$x - y$$$.
  • Деление с округлением вниз: вы выбираете целое число $$$z$$$ от $$$2$$$ до $$$x$$$ включительно и перемещаете токен из ячейки $$$x$$$ в ячейку $$$\lfloor \frac{x}{z} \rfloor$$$ (частное от деления $$$x$$$ на $$$z$$$ с округлением вниз).

Найдите число способов, которыми токен может добраться из ячейки $$$n$$$ в ячейку $$$1$$$ за один или более сдвигов, и выведите это число по модулю $$$m$$$. Обратите внимание, что если есть несколько способов переместить токен из одной ячейки в другую за один сдвиг, все эти способы считаются различными (смотрите пояснение к примерам для лучшего понимания).

Входные данные

Единственная строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$10^8 < m < 10^9$$$; $$$m$$$ — простое число) — длину полоски и число, по модулю которого необходимо вычислить ответ.

Выходные данные

Выведите число способов для токена добраться из ячейки $$$n$$$ в ячейку $$$1$$$, по модулю $$$m$$$.

Примеры
Входные данные
3 998244353
Выходные данные
5
Входные данные
5 998244353
Выходные данные
25
Входные данные
42 998244353
Выходные данные
793019428
Примечание

В первом тесте есть три способа добраться из ячейки $$$3$$$ в ячейку $$$1$$$ за один сдвиг: с помощью вычитания $$$y = 2$$$, а также с помощью деления на $$$z = 2$$$ или $$$z = 3$$$.

Также есть два способа добраться из ячейки $$$3$$$ в ячейку $$$1$$$ через ячейку $$$2$$$: сначала вычесть $$$y = 1$$$, а потом либо снова вычесть $$$y = 1$$$, либо поделить на $$$z = 2$$$.

Таким образом, всего способов пять.