AT_awc0002_e お菓子の詰め合わせ

高桥在一家糖果店里发现了 $N$ 种糖果。第 $i$ 种糖果的价格是 $A_i$ 日元（$1 \leq i \leq N$）。由于每种糖果仅有一件，他对于每种糖果只能选择“买”或“不买”。需要注意的是，不同种类的糖果可能价格相同，但它们仍被认为是不同的糖果。 高桥恰好有 $S$ 日元。为了最大化利用这些钱，他希望购买若干种糖果，使得总价格恰好为 $S$ 日元，且一分钱也不剩。 在从这 $N$ 种糖果中选择 $0$ 个或若干种糖果的所有方法中，求使得所选糖果总价格恰好为 $S$ 日元的方法数。注意，如果没有选任何糖果，则总价格被认为是 $0$ 日元。

> $N$ $S$ > $A_1$ $A_2$ $\ldots$ $A_N$ - 第一行包含两个整数 $N$（表示糖果种类数）和 $S$（高桥拥有的钱数），两者用空格隔开。 - 第二行包含 $A_1, A_2, \ldots, A_N$，表示每种糖果的价格，数字之间用空格隔开。

输出一行，表示选取糖果使其总价格恰好为 $S$ 日元的方法数。

### 数据范围 - $1 \leq N \leq 40$ - $0 \leq S \leq 10^{12}$ - $1 \leq A_i \leq 10^{12}$ - 所有输入均为整数。 由 ChatGPT 5 翻译