2499: 奇怪的桌子
内存限制：256 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：4
解决：3
题目描述
小 H 有一张奇怪的矩形桌子,他能在桌子上的格子内画点,一个格子最多只能画一个点。
这个桌子是 N*M 的,现在小 H 想知道有多少种不同的放法能使得桌子上每个 N*N 的正方形内
恰好有 K(0≤K≤N^2)个点。
小 H 智商有限,所以他希望你能帮他解决这个问题。因为方案数可能有很多,所以你只
需要输出方案数除以 1000000007 (10^9+7)的余数。
输入
一行三个正整数 N,M,K。分别表示桌子的宽,长,和 N*N 正方形中点的数目。
输出
一行一个正整数 ANS,表示最后的方案数。
样例输入 复制
5 6 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。