CF232B.Table

John Doe has an n × m table. John Doe can paint points in some table cells, not more than one point in one table cell. John Doe wants to use such operations to make each square subtable of size n × n have exactly k points.

John Doe wondered, how many distinct ways to fill the table with points are there, provided that the condition must hold. As this number can be rather large, John Doe asks to find its remainder after dividing by 1000000007 (109 + 7).

You should assume that John always paints a point exactly in the center of some cell. Two ways to fill a table are considered distinct, if there exists a table cell, that has a point in one way and doesn't have it in the other.

约翰·多伊有一个 $n \times m$ 的表格。约翰·多伊可以在某些表格单元格中绘制点，每个单元格至多绘制一个点。约翰·多伊希望经过若干次这样的操作，使得每个大小为 $n \times n$ 的正方形子表格中恰好包含 $k$ 个点。

约翰·多伊想知道：在满足上述条件的前提下，有多少种不同的方式向表格中绘制点？由于该数目可能非常大，约翰·多伊要求输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。

你应假设约翰总是将点精确地绘制在某个单元格的中心位置。若存在某个表格单元格，在一种方式中有绘制点、而在另一种方式中没有，则称这两种填表方式是不同的。

A single line contains space-separated integers n, m, k (1 ≤ n ≤ 100; n ≤ m ≤ 1018; 0 ≤ k ≤ _n_2) — the number of rows of the table, the number of columns of the table and the number of points each square must contain.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

一行包含三个以空格分隔的整数 $n$、$m$、$k$（$1 ≤ n ≤ 100$；$n ≤ m ≤ 10^{18}$；$0 ≤ k ≤ n^2$）—— 分别表示表格的行数、列数，以及每个方格必须包含的点数。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

In a single line print a single integer — the remainder from dividing the described number of ways by 1000000007 (109 + 7).

在一行中输出一个整数——即所述方案数对 1000000007（$10^9 + 7$）取模的余数。

Let's consider the first test case:

The gray area belongs to both 5 × 5 squares. So, if it has one point, then there shouldn't be points in any other place. If one of the white areas has a point, then the other one also must have a point. Thus, there are about 20 variants, where the point lies in the gray area and 25 variants, where each of the white areas contains a point. Overall there are 45 variants.

我们来考虑第一个测试用例：

灰色区域同时属于两个 $5 \times 5$ 的正方形。因此，若该区域内存在一个点，则其余任何位置均不得再有其他点；若其中一个白色区域中存在一个点，则另一个白色区域中也必须存在一个点。于是，共有约 20 种情况满足点位于灰色区域内，另有 25 种情况满足每个白色区域中各有一个点。总计共有 45 种情况。