LGTB新买了一张n*m的矩(桌)阵(子)，他想给某些1*1的小矩形染色，使得染色之后，原矩阵的每个n*n的子矩阵中都包含恰好k个被染色了的小矩形。他想知道有多少种染色方案能让他满足上述要求。因为答案肯呢个很大，请输出方案数膜1e9+7的值

输入

输入第一行包含三个整数n，m，k，意义如题面所示

对于15%的数据，1≤n*m≤20，n≤m

对于40%的数据，1≤n≤10，n≤m≤1000

对于100%的数据，1≤n≤100，n≤m≤1e18,0≤k≤n²

输出

输出包含1个整数，代表LGTB的方案数

样例

样例输入

5 6 1

样例输出

45

时间限制

3s

样例说明

 

样例如图所示，如果在灰色区域染一个格子，有20种方案。如果在两边的白色格子各染一个格子，有25种方案。共45种方案。

 

 

由于题目描述中m最大是1e18，所以肯定要用到快速幂。

首先我们可以发现，如果把一列捆在一起处理的话，那么为了满足题意，第i列一定与第i+n列的染色个数是相同的。

那么考虑DP[i][j]，代表每一个整个块(如1~n为一块，n+1~2*n为一块，因为他们每一列的染色个数相同)中处理了前i列，此时染了j个颜色的方案数。

那么如果考虑下一块的话，设下一块染色个数为kk，则增加的方案数就为C[n][k]^t[i](t[i]为i位置存在的总个数)

于是C[n][k]用杨辉三角求出，然后在快速幂求C[n][k]^t[i]。

这里会发现，有可能最后要多出一点，也就是部分块，那么他们的列数要+1。

处理完过后，就可以直接DP了。时间复杂度O(n^4)

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 const int maxn=105; 7 const long long mod=1e9+7; 8 int n,k;long long m; 9 long long c[maxn][maxn];10 long long dp[maxn][maxn*maxn];11 long long w[2][maxn];long long re;12 long long qe(long long a,long long b)13 {14     long long qwe=1;15     while(b)16     {17         if(b&1)qwe*=a;18         if(qwe>mod)qwe%=mod;19         b>>=1;a=a*a;20         if(a>mod)a%=mod;21     }22     return qwe;23 }24 void init()25 {26     c[0][0]=1;27     for(int i=1;i<=100;i++)28     for(int j=0;j<=i;j++)29     {30         c[i][j]=c[i-1][j]+c[i-1][j-1];31         if(c[i][j]>mod)c[i][j]%=mod;32     }33     long long qwe=m/n;34     re=m%n;35     for(int i=0;i<=n;i++)36     {37         w[0][i]=qe(c[n][i],qwe);38         w[1][i]=qe(c[n][i],qwe+1);39     }40     return ;41 }42 int main()43 {44     freopen("table.in","r",stdin);45     freopen("table.out","w",stdout);46     scanf("%d%I64d%d",&n,&m,&k);47     init();48     dp[0][0]=1;49     long long wer=0;50     for(int i=0;i