Чанека, прирождённый геймер, изобрела новый игровой контроллер под названием «Джойборд». Интересно, что изобретенный ею джойборд можно использовать только для одной игры.
На джойборде имеется экран, содержащий $$$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$$$?
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 2\cdot10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n \leq 10^9$$$; $$$0 \leq m \leq 10^9$$$; $$$1 \leq k \leq n+1$$$): всего имеется $$$n+1$$$ слотов, значение в слоте $$$n+1$$$ не должно быть больше $$$m$$$, и в итоговом массиве должно быть ровно $$$k$$$ различных значений.
Для каждого набора входных данных в отдельной строке выведите количество допустимых способов присвоения целого неотрицательного числа в слот $$$n+1$$$.
44 6 32 0 1265 265 2653 10 2
2 1 0 5
В первом наборе входных данных одним из $$$2$$$ возможных способов для Чанеки является выбор $$$a_{n+1}=6$$$. Если она это сделает, то:
Во втором наборе входных данных для Чанеки возможен $$$1$$$ вариант — выбрать $$$a_{n+1}=0$$$. Если она это сделает, то $$$a = [0, 0, 0]$$$. Существует только $$$1$$$ значение.
В третьем наборе входных данных не существует возможного способа присвоения целого неотрицательного числа в слот $$$n+1$$$.
Название |
---|