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
注意
让我们考虑第一个测试用例: