← 返回题目列表

AtCoder · xmascon17_d

D. 反转数

中文机器翻译题面 查看原题

配点 : 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 后的余数。