题目描述

Smart 有一张奇怪的矩形桌子，他能在桌子上的格子内画点，一个格子最多只能画一个点。这个桌子是 \(N×M\) 的，现在 Smart 想知道有多少种不同的放法能使得桌子上每个 \(N×N\) 的正方形内恰好有 \(K（ 0 ≤K≤N^2）\)个点。
Smart 智商有限，所以他希望你能帮他解决这个问题。因为方案数可能有很多，所以你只需要输出方案数除以 \(1000000007 \) 的余数。

格式

输入格式

三个正整数 \(N,M,K\)。分别表示桌子的宽，长，和 \(N×N\) 正方形中点的数目。

输出格式

一个正整数，表示最后的方案数。

样例1

样例输入1

5 6 1

样例输出1

45

样例解释

灰色区域同时属于 \(2\) 个 \(5×5\) 的正方形，所以可以在期中的任意一个位置放一个，共有 \(20\) 种。当然也可以在 \(2\) 个白色区域都各放一个，共有 \(5×5=25\) 种。所以共有 \(45\) 种。

限制

\(10\%\) 的数据满足 \(4≤N×M≤10\)
另外 \(20\%\) 的数据满足 \(1≤N=M≤100\)
\(100\%\) 的数据满足 \(1≤N≤100,N≤M≤10^{18}\)