Последовательность целых чисел \(b_1, b_2, \ldots, b_m\) называется хорошей, если \(max(b_1, b_2, \ldots, b_m) \cdot min(b_1, b_2, \ldots, b_m) \ge b_1 + b_2 + \ldots + b_m\).
Последовательность целых чисел \(a_1, a_2, \ldots, a_n\) называется идеальной, если каждая непустая подпоследовательность \(a\) является хорошей.
У YouKn0wWho есть два целых числа \(n\) и \(M\), \(M\) — простое. Помогите ему найти количество, по модулю \(M\), идеальных последовательностей \(a_1, a_2, \ldots, a_n\) таких, что \(1 \le a_i \le n + 1\) для каждого \(i\) от \(1\) до \(n\).
Последовательность \(d\) является подпоследовательностью последовательности \(c\), если \(d\) может быть получена из \(c\) путем удаления нескольких (возможно, нуля или всех) элементов.
Выходные данные
Выведите одно целое число — количество идеальных последовательностей по модулю \(M\).
Примечание
В первом примере идеальные последовательности — \([2, 2]\), \([2, 3]\), \([3, 2]\) и \([3, 3]\).
Во втором примере, некоторые из идеальных последовательностей — \([3, 4, 3, 5]\), \([4, 5, 4, 4]\), \([4, 5, 5, 5]\) и т.д. Одним из примеров последовательности, которая не является идеальной, является \([2, 3, 3, 4]\), потому что, например, подпоследовательность \([2, 3, 4]\) не является хорошей, так как \(2 \cdot 4 < 2 + 3 + 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 998244353
|
4
|
|
2
|
4 100000007
|
32
|
|
3
|
69 999999937
|
456886663
|