問題文

要素数 N の順列とは、1 から N までの N 個の整数 (1, 2, ..., N) を並べ替えたものです。

要素数 N の順列 A に対し、A の転倒数 (inversion number) とは、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 で割った余りを出力してください。