问题描述

给定 $n$ 个正整数 $a_1, a_2, \dots, a_n$，你可以从中选择任意多个数（可以选择 $0$ 个，也可以选择全部）。

请你计算共有多少种选择方案，使得所选数字的和严格小于给定的整数 $x$。

注意，不同的选择方案是指选择的元素下标集合不同，即使选出的数字之和相同，也视为不同方案。

输入格式

第一行包含两个整数 $n$ 和 $x$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

输出一个整数，表示满足条件的选择方案总数。

样例输入

3 5
1 2 3

样例输出

6

说明

共有 $2^3 = 8$ 种选择方案：

• 不选任何数，和为 $0$，满足条件
• 选 $1$，和为 $1$，满足条件
• 选 $2$，和为 $2$，满足条件
• 选 $3$，和为 $3$，满足条件
• 选 $1,2$，和为 $3$，满足条件
• 选 $1,3$，和为 $4$，满足条件
• 选 $2,3$，和为 $5$，不满足条件
• 选 $1,2,3$，和为 $6$，不满足条件

共 $5$ 种方案满足所选数字之和小于 $5$。

评测数据规模

对于所有数据，满足：

$1 \le n \le 20$

$1 \le x \le 10^9$

$1 \le a_i \le 10^9$