题目描述

长征途中，红军有两支总队正在行军。后方有 $n$ 件物资需要分配给前线部队。每件物资可以有三种分配方式：

1. 分配给第一纵队
2. 分配给第二纵队
3. 暂时留作战略储备

由于运输能力有限，最多只能留 $m$ 件物资作为预备。

为了保留两纵队的公平，要求两纵队获得的物资总重量必须相等，物资重量为 $w_1,w_2,\dots,w_n$。

问：有多少种分配方式？

注意：两边都不分配，即所有物资都留做预备也算一种方案 $(n\leq m)$。

输入格式

第一行：两个正整数 $n\ m$，分别表示物资总数，预备上限

第二行：$n$ 个正整数 $w_1,w_2,\ldots,w_n$，表示各物资重量，空格分割

输出格式

输出一个整数，表示满足条件的分配方案数量

样例

3 3
1 2 3

3

3 1
1 2 3

2

4 0
2 3 5 10

2

数据范围