← 返回题目列表

Codeforces · 232/B

B. 表

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

John Doe 有一个 n × m 表。 John Doe 可以在某些表格单元格中绘制点,但一个表格单元格中最多只能绘制一个点。 John Doe 想要使用这样的操作来使每个大小为 n × n 的方形子表恰好有 k 个点。

John Doe 想知道,如果条件必须成立,那么有多少种不同的方法可以用点填充表格。由于这个数字可能相当大,John Doe 要求求出除以 1000000007 (109 + 7) 后的余数。

您应该假设 John 总是在某个单元格的中心精确地绘制一个点。如果存在一个表格单元格,该表格单元格在一种方式中有一个点而在另一种方式中没有,则两种填充表格的方式被认为是不同的。

输入

单行包含空格分隔的整数 n、m、k (1 ≤ n ≤ 100; n ≤ m ≤ 1018; 0 ≤ k ≤ n2) — 表格的行数、表格的列数以及每个方格必须包含的点数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

在一行中打印一个整数 - 将所描述的路数除以 1000000007 (109 + 7) 所得的余数。

示例

输入 #1

5 6 1

输出 #1

45

注意

让我们考虑第一个测试用例: