题意
求满足：(sumlimits_{i=1}^m a_ile S)，(forall i,a_i>0)，(a_ile T(ile n))。
(nle mle 10^9,Tle 10^5,n imes Tle Sle 10^{18},m−nle 1000)
做法一
考虑容斥：(sumlimits_{i=0}^n (-1)^i {nchoose i}{S-iTchoose m})
等价于([x^m]((1+x)^T-1)^n(1+x)^{S-nT})
证明：
考虑组合意义
有(S)个位置，每个位置染黑白两色，这些位置分成(n+1)块，前(n)块每块有(T)个位置，最后一块有(S-nT)个位置。恰好m个位置为黑色，前面(n)块每块至少有一个位置被染黑
然后((1+x)^T-1)的常数项为(0)，所以(((1+x)^T-1)^n)的([0,n))次项均为0，所以答案等价于([x^{n-m}]frac{((1+x)^T-1)^n(1+x)^{S-nT}}{x^n})
除掉(x^n)，可以看作在进行(((1+x)^T-1))的(n)次方前整体往前移一位，所以在快速幂的时候要保留([0,n-m+1])次