Description:


\(N\) 个盒子,每个盒子里面有一种颜色的花,数量为 \(S_i\)\(N\) 个盒子里花的颜色各不相同,但同一个盒子里面的花认为是相同的,现在需要选出 \(K\) 朵花,有多少种不同的方案?由于结果很大,输出Mod \(1000000007\) 的结果即可。
例如: \(3\) 个盒子,花的数量分别为 \(1,3,2\) ,需要选出 \(5\) 朵花,那么可以有如下 \(3\) 种方案:{ \(1,2, 2\) }, { \(0, 3, 2\) }, { \(1, 3, 1\) }。

Input:


\(1\) 行:两个数 \(N, K\)\(N\) 为盒子的数量, \(K\) 为需要的花朵的数量( \(1\le N\le 20, 1\le K\le 10^{18}\) )
\(2\sim N + 1\) 行:每行 \(1\) 个数,对应盒子中花朵的数量 \(S_i\) ( \(1\le S_i \le 10^{16}\) )

Output:


输出方案的数量Mod \(1000000007\)

Sample Input:


Sample Output:


题解:


这道题还是有一些难度的。

如果我们不考虑 \(S_i\) 的限制,那么就是把 \(K\) 分为 \(n\) 份,答案就是 \(\binom{n+K-1}{n-1}\)

现在我们加了 \(n\) 条限制,注意到 \(n\le 20\) ,我们可以考虑容斥。

我们枚举每一条限制是否满足,如果不满足我们把 \(K\) 减去 \(S_i+1\) ,这种情况的贡献就是 \((-1)^c \times \binom{n+K-1}{n-1}\) ,其中 \(c\) 表示不满足的数目。

因为 \(n\) 很小,组合数 \(\binom{n+K-1}{n-1}\) 可以根据 \(\binom{n}{m} = \binom{n}{m-1}\times \frac{n-m+1}{m}\)\(O(n)\) 时间内递推出来。

注意 \(K\) 极大,也就是说把 \(K\) 带入组合数运算时应先取模。(因为这个WA了很久╮(╯▽╰)╭)