Sunrise Festival

题号：NC293652
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ Saki 已经受不了这帮队友了，感觉自己人格都要分裂了，所以要决定退出乐队加入吹奏部。
$\hspace{15pt}$ 这周末要举办端午节纪念巡游活动，当地每个学校的吹奏部都要派表演方阵进行巡游表演，saki 学校的吹奏部也要参加这次活动，按照纪念巡游的活动传统，会对巡游的表演方阵有统一的要求。

$\hspace{15pt}$ 吹奏部有 $n$ 名部员，saki 作为吹奏部的一员，负责从 $n$ 名部员中选择若干名部员组成「 $k$ 人方阵」来参加活动。这是指一个由吹奏部部员组成的表演方阵，首先必须有一个领队站在前面，方阵有若干排（可以 $0$ 排），但每排必须是 $k$ 个人。
$\hspace{15pt}$ 请你帮 Saki 计算一下有多少种不同的「 $k$ 人方阵」选法？由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

$\hspace{15pt}$ 注意 saki 只要选出若干名部员，能够组成「 $k$ 人方阵」就可以了，不需要去安排每个人的分工和站的位置，对是否是领队不作区分。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
在一行上输入两个整数  代表吹奏部的部员人数、  人方阵的每排人数。

输出描述:

对于每一组测试数据，新起一行。输出一个整数，表示有多少种不同的「 人方阵」选法。

示例1

输入

复制

输出

复制

341
16
211585

说明

对于第三组测试数据，一共有四种排数不同的「 人方阵」选法，分别是：
       |      👧   |       👧👧   |       👧👧👧
       |      👧   |       👧👧   |       👧👧👧
⭐     |     ⭐👧   |    ⭐👧👧   |    ⭐👧👧👧
       |      👧   |       👧👧   |       👧👧👧
       |      👧   |       👧👧   |       👧👧👧
有公式 。

题目描述

输入描述:

输出描述:

输入

输出

说明

备注: