CF1877C Joyboard

Chaneka 是一名游戏玩家，她发明了一种新的游戏手柄，名为 joyboard。有趣的是，她发明的 joyboard 只能用来玩一种游戏。 joyboard 上有一个屏幕，包含 $n+1$ 个槽位，从左到右编号为 $1$ 到 $n+1$。这 $n+1$ 个槽位将被填入一个非负整数数组 $[a_1,a_2,a_3,\ldots,a_{n+1}]$。作为玩家的 Chaneka 必须为 $a_{n+1}$ 赋值一个 $0$ 到 $m$（包含 $0$ 和 $m$）之间的整数。然后，对于每个 $i$ 从 $n$ 到 $1$，$a_i$ 的值等于其右侧相邻值 $a_{i+1}$ 除以 $i$ 的余数。换句话说，$a_i = a_{i + 1} \bmod i$。 Chaneka 希望在所有槽位都被赋值后，整个屏幕上恰好有 $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$ 赋值非负整数。

在第一个测试用例中，Chaneka 有 $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$ 个不同的值。 在第二个测试用例中，Chaneka 只有 $1$ 种可能的方式，即选择 $a_{n+1}=0$。如果她这样做，则 $a = [0, 0, 0]$，屏幕上只有 $1$ 个不同的值。 在第三个测试用例中，没有任何方式可以为槽位 $n+1$ 赋值非负整数。 由 ChatGPT 4.1 翻译