Чанека, прирождённый геймер, изобрела новый игровой контроллер под названием «Джойборд». Интересно, что изобретенный ею джойборд можно использовать только для одной игры.
На джойборде имеется экран, содержащий \(n+1\) слотов, пронумерованных от \(1\) до \(n+1\) слева направо. Все \(n+1\) слотов заполняются массивом целых неотрицательных чисел \([a_1,a_2,a_3,\ldots,a_{n+1}]\). Чанека, как игрок, должна присвоить \(a_{n+1}\) целое число от \(0\) до \(m\) включительно. Тогда для каждого \(i\) от \(n\) до \(1\) значение \(a_i\) будет равно остатку от деления \(a_{i+1}\) (соседнего справа значения) на \(i\). Другими словами, \(a_i = a_{i + 1} \bmod i\).
Чанека хочет, чтобы после присвоения каждому слоту целого числа на всем экране (среди всех слотов \(n+1\)) было ровно \(k\) различных значений. Сколько существует допустимых способов присвоения целого неотрицательного числа слоту \(n+1\)?
Выходные данные
Для каждого набора входных данных в отдельной строке выведите количество допустимых способов присвоения целого неотрицательного числа в слот \(n+1\).
Примечание
В первом наборе входных данных одним из \(2\) возможных способов для Чанеки является выбор \(a_{n+1}=6\). Если она это сделает, то:
- \(a_4=a_5\bmod 4=6\bmod 4=2\)
- \(a_3=a_4\bmod 3=2\bmod 3=2\)
- \(a_2=a_3\bmod 2=2\bmod 2=0\)
- \(a_1=a_2\bmod 1=0\bmod 1=0\)
- \(a = [0, 0, 2, 2, 6]\)
- Существует \(3\) различных значения.
Во втором наборе входных данных для Чанеки возможен \(1\) вариант — выбрать \(a_{n+1}=0\). Если она это сделает, то \(a = [0, 0, 0]\). Существует только \(1\) значение.
В третьем наборе входных данных не существует возможного способа присвоения целого неотрицательного числа в слот \(n+1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 6 3
2 0 1
265 265 265
3 10 2
|
2
1
0
5
|