#P18651. 5

5

5

给定一个长度为 nn、由非负整数组成的数组 aa。请计算满足下列条件的整数对 (k,T)(k,T) 的数量:存在一个长度为 kk 的 aa 的子序列,其元素之和恰好为 TT。

不过,这个问题实在太一般了。设数组中所有元素的和为 SS,保证数组中至少有 S/5S/5 个元素等于 11。

子序列可以通过从原数组中删除若干元素得到,保留的元素顺序不变。空子序列也计入,因此 (0,0)(0,0) 是一个满足条件的整数对。不同子序列若对应同一个 (k,T)(k,T),这个整数对只计一次。

输入格式

第一行两个正整数 n,Sn,S(1≤n,S≤2⋅1051\le n,S\le2\cdot10^5),分别表示数组长度和所有元素之和。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai≤S0\le a_i\le S)。

保证 ∑i=1nai=S\sum_{i=1}^n a_i=S,并且至少有 S/5S/5 个元素等于 11。当 SS 不是 55 的倍数时,这个条件等价于 5⋅#{i:ai=1}≥S5\cdot\#\{i:a_i=1\}\ge S。

输出格式

输出满足条件的整数对 (k,T)(k,T) 的数量。

样例输入 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