SP20689 WRP - WA,RTE and Placements

在**外星人机器学习学院**（ACM），招聘季已经拉开帷幕，所有的外星人都在加紧准备。然而，作为学院的尖子生和最抢手的单身汉，威廉·阿彻（WA）却显得无动于衷，将时间全部花在与他的朋友瑞哈娜（RTE）共度时光上，忽视了学业。RTE 为了帮助 WA 在不影响学习的情况下，保证与她的约会时间，设计了一个计划。在经过与好友 AC 的讨论后，她为 WA 提出了如下安排： 1. RTE 将 WA 接下来的 **N** 小时分成 **K** 个时段。 2. 每个时段的持续时间 **x** 是一个整数，满足 **1 ≤ x ≤ M**。 3. 在每个时段内，WA 可以选择学习或与 RTE 见面。 4. 如果 WA 在某个时段学习了，那么他在下一个时段必须与 RTE 见面，反之亦然。 5. WA 必须在第一个时段学习。 你需要帮助 WA 计算，对于接下来的 N 小时内，RTE 可以为 WA 制定多少种不同的安排方式。 ### 输入格式 第一行为测试用例数 T，接下来的 T 行每行包括 3 个整数：N、K 和 M。 ### 输出格式 对于每个测试用例，输出一个整数，表示 RTE 可以准备的不同时间安排的数量，并对 $1000000007$ 取模。 ### 数据范围与提示 - $$T \leq 100$$ - $$1 \leq N, K, M \leq 100000$$ - $$K \leq N$$ **本翻译由 AI 自动生成**

无

无