SP15851 PSERVICE - Permutations

某网站为用户提供多种服务。该网站一共有 **K** 种服务可供使用。目前，有 **M** 名用户/客户注册了该网站。 每位用户需要被分配一个项目，该项目由长度为 **N** 的一系列服务构成，表示为 **A1, A2, A3, ..., An**，这些服务都来自于网站现有的服务列表。执行服务时的顺序是有要求的（例如，编译后再链接与链接后再编译是不同的顺序）。并且，在同一项目中，不能连续两次执行相同的服务。例如，编译 → 链接 → 编译是可行的，但链接 → 链接 → 编译则不可行，因为“链接”服务连续出现了两次。 所有的 **M** 名用户会同时开始他们的项目，而每项服务的执行时间是相同的。由于只有一台服务器，同时只允许一个用户访问某个服务。例如，假设有 3 名用户，他们各自的项目分别是 **A1, A2, ..., An**；**B1, B2, ..., Bn** 和 **C1, C2, ..., Cn**，那么对于任意的 1 ≤ **i** ≤ **N**，**Ai**、**Bi** 和 **Ci** 必须两两不同。你的任务是计算将 **M** 名用户项目进行这样的分配，有多少种不同的方法。

第一行包含一个整数 **T**，表示测试用例的数量。 接下来每个测试用例包含一行，包含三个整数 **N**、**M** 和 **K**。

对于每个测试用例，输出一个整数，表示分配项目的不同方法数，结果需要对 1000000007 取模。

- 1 ≤ T ≤ 10 - 0 ≤ N ≤ 1000000000 - 1 ≤ M ≤ 100 - 0 ≤ K ≤ 1000 **样例输入** ``` 3 2 2 3 1 2 3 2 3 4 ``` **样例输出** ``` 18 6 264 ``` **本翻译由 AI 自动生成**