a480. CPE：Arrange the Numbers (UVa 11481)

題目描述

將整數 1, 2, …, N 重新排列，每個整數都必須恰好使用一次。原始序列中，數字 i 位在第 i 個位置；重新排列後若仍然如此，就稱這個位置保持不變。

請計算有多少種排列，使前 M 個位置中恰好有 K 個位置保持不變。第 M + 1 到第 N 個位置不受這項條件限制，可以保持不變，也可以改變。

答案可能很大，請輸出排列數除以 1000000007 的餘數。

來源：CPE 2026/05/26 第 7 題，UVa 11481 — Arrange the Numbers。本敘述依原題規格重新撰寫；題名採用 UVa 原題名稱。

輸入格式

第一行為測試資料組數 T，T ≤ 1000。

接下來 T 行，每行包含三個整數 N M K，滿足 1 ≤ N ≤ 1000、M ≤ N、K ≤ M。M 與 K 分別表示要檢查的位置數與其中保持不變的位置數，皆為非負整數。

輸出格式

每組資料輸出一行 Case x: y，其中 x 是從 1 開始的資料編號，y 是符合條件的排列數對 1000000007 取餘數後的值。冒號後恰有一個空白，不需額外輸出空白行。