题面：受限的选择

时间限制： 1 秒 内存限制： 256 MB

给定一个包含 n 个正整数的序列 a1, a2, ..., an，你可以对每个数独立决定是否选择它。

如果被选择的所有数字之和不超过 S，则认为这是一种合法方案。

请你计算合法方案的数量。

输入格式

第一行包含两个整数 n, S，表示数字个数和允许的最大和。

第二行包含 n 个整数 a1, a2, ..., an。

输出格式

输出一个整数，表示合法选择方案的数量。

数据范围

对于所有测试点：

1 <= n <= 20
0 <= S <= 10^18
1 <= ai <= 10^9

保证答案不超过 2^n。

样例

输入

3 5
1 2 3

输出

7

说明

一共有 2^3 = 8 种选择方式。

只有选择 1, 2, 3 三个数字时，总和为 6，超过 5，不合法。

因此合法方案数为 7。

4. 测试点说明表