Bảng điểm

Cho một bảng gồm $n$ hàng và $m$ cột. Ta có thể đánh dấu một số ô của bảng, mỗi ô đánh dấu nhiều nhất một điểm.

Một bảng con vuông kích thước $n\times n$ là một khối gồm $n$ hàng và $n$ cột liên tiếp của bảng. Hãy đếm số cách đánh dấu điểm sao cho mọi bảng con vuông kích thước $n\times n$ đều chứa đúng $k$ điểm.

Hai cách đánh dấu được coi là khác nhau nếu tồn tại một ô có điểm ở cách này nhưng không có điểm ở cách kia.

Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

Một dòng duy nhất chứa ba số nguyên $n$, $m$, $k$.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách đánh dấu thỏa mãn, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 100$
• $n\le m\le {10}^{18}$
• $0\le k\le n^2$

Ví dụ