配点 : 100 点
問題文
要素数 N 的排列是,1 从 N 由 N 整数 (1, 2, ..., N) 的重新排列。
要素数 N 的置换 A , 非负整数A 的逆序数(倒数)是,A_i > A_j 满足的组合 (i, j) (1 \leq i < j \leq N)的个数。
要素数 N 的排列中,其逆序数被 K 除后的余数 m 的个数是 10^9+7 求余数。
制約
- 1 \leq N \leq 10^{18}
- 0 \leq m < K \leq 10
入力
N K m
出力
要素数 N 的排列中,其逆序数被 K 除后的余数 m 的个数是 10^9+7 后的余数。
入力例 1
3 10 2
出力例 1
2
要素数 3 的排列的逆序数最多为 3 ,因此在此情况下只需数逆序数为 2 的。
逆序数为 2 的排列是 (3, 1, 2), (2, 3, 1) 的 2 种。
入力例 2
7 9 1
出力例 2
599
入力例 3
100 1 0
出力例 3
437918130
10^9+7 后的余数。