给定一个长度为 $n$ 的非负整数数组 $a$。计算满足以下条件的数对 $(k, T)$ 的数量：存在一个长度为 $k$ 的 $a$ 的子序列，其元素之和等于 $T$。

开个玩笑，这太一般了。假设 $a$ 中所有元素的和为 $S$，已知 $a$ 中至少有 $S/5$ 个元素等于 $1$。

输入格式

第一行包含两个正整数 $n$ 和 $S$ ($1 \le n, S \le 2 \cdot 10^5$)，分别表示数组 $a$ 的长度及其元素之和。

第二行包含数组 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le S$)。保证 $\sum_{i=1}^n a_i = S$，且 $a$ 中至少有 $S/5$ 个元素等于 $1$。

输出格式

输出满足以下条件的数对 $(k, T)$ 的数量：存在一个长度为 $k$ 的 $a$ 的子序列，其元素之和等于 $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