M-晚饭吃什么？_2025年华为杯广东工业大学程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

“晚饭吃什么？” “我都行。”

notPP 罗列了 $m$ 个吃饭的地点，在接下来的 $n$ 天中，notPP 觉得一直吃外卖会腻，于是他决定拿恰好 $k$ 天出来去外面吃饭。

但连续两天都在同一个地方吃饭容易腻，于是他希望“不能连续两天都去同一个地方吃饭（外卖除外）”的规则。

在这种情况下，请问 notPP 有多少种方案呢？因为答案可能很大，所以请将其对 $10^9+7$ 取模。

本题每个测试点有多组测试数据。

第一行输入一个正整数 $T$ ( $1 \leq T \leq 10^5$ )，表示有 $T$ 组测试样例。

接下来对于每组样例：

一行输入三个数字 $n,m,k$ ( $1 \leq k \leq n \leq 10^6$ , $1 \leq m \leq 10^6$ )，分别代表接下来 $n$ 天，有 $m$ 个吃饭的地方和分配 $k$ 天。

保证单个测试点的所有测试数据的 $n$ 之和不超过 $10 ^ 6$ 。

输出一行，表示分配方案的数量对 $10^9+7$ 取模得到的结果。

示例1

复制

2
3 2 3
3 2 2

复制

2
8

对于第一个样例，notPP在接下来的 $3$ 天都去外面吃，故有两种情况： $\{1,2,1\}$ 和 $\{2,1,2\}$ 。

对于第二个样例，这里有所有的可行情况（其中 $0$ 表示外卖）：

$\{1,2,0\},\{2,1,0\},\{1,0,1\},\{1,0,2\},\{2,0,1\},\{2,0,2\},\{0,1,2\},\{0,2,1\}$