Эта версия задачи отличается от следующей только ограничением на \(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\). Обратите внимание, что если есть несколько способов переместить токен из одной ячейки в другую за один сдвиг, все эти способы считаются различными (смотрите пояснение к примерам для лучшего понимания).
Примечание
В первом тесте есть три способа добраться из ячейки \(3\) в ячейку \(1\) за один сдвиг: с помощью вычитания \(y = 2\), а также с помощью деления на \(z = 2\) или \(z = 3\).
Также есть два способа добраться из ячейки \(3\) в ячейку \(1\) через ячейку \(2\): сначала вычесть \(y = 1\), а потом либо снова вычесть \(y = 1\), либо поделить на \(z = 2\).
Таким образом, всего способов пять.