#P18651. 5
5
5
给定一个长度为 、由非负整数组成的数组 。请计算满足下列条件的整数对 的数量:存在一个长度为 的 的子序列,其元素之和恰好为 。
不过,这个问题实在太一般了。设数组中所有元素的和为 ,保证数组中至少有 个元素等于 。
子序列可以通过从原数组中删除若干元素得到,保留的元素顺序不变。空子序列也计入,因此 是一个满足条件的整数对。不同子序列若对应同一个 ,这个整数对只计一次。
输入格式
第一行两个正整数 (),分别表示数组长度和所有元素之和。
第二行 个整数 ()。
保证 ,并且至少有 个元素等于 。当 不是 的倍数时,这个条件等价于 。
输出格式
输出满足条件的整数对 的数量。
样例输入 1
7 9
0 0 0 1 1 2 5
样例输出 1
42
样例输入 2
10 33
9 9 8 1 1 1 1 1 1 1
样例输出 2
48
样例输入 3
10 14
2 4 4 1 0 1 0 1 0 1
样例输出 3
81
样例输入 4
10 14
3 5 3 0 1 0 1 0 1 0
样例输出 4
87