SP30351 NPC2016E - Quest Hunter

塔塔玛大陆正面临一场危机。一条巨龙苏醒了，它将这片土地化为灰烬。听闻此事，菲欧、瓦卡和温波三个勇士决定成立公会「任务猎人」，以图消灭恶龙。 为了打败这条巨龙，他们需要先购置武器。他们来到 J0I 铁匠铺，这里出售 $N$ 件武器，每件武器的价格为 $X_i$ 金币。「任务猎人」目前只有 $Y$ 金币，他们想用这笔钱尽可能多地买到武器。 买完武器后，他们前往本地的酒馆准备雇佣士兵加入公会。每位雇佣兵都需要配备一件他们刚买的武器。不过，好运不常在，「任务猎人」弄丢了清单，完全不记得每件武器的具体价格。于是，他们决定给每件武器随机定价，条件是：没有武器可以定价为 0 金币，而且所有武器的总价必须等于购买时花费的总金币数。现在，他们想知道有多少种可能的定价组合。由于组合数可能非常庞大，请输出其对 $10^9 + 7$ 取模后的结果。

第一行是一个整数 $T$，代表测试用例的数量。 对于每个测试用例： - 第一行是一个整数 $N$，表示武器的数量。 - 第二行有 $N$ 个整数 $X_i$，代表每件武器的原价。 - 第三行是一个整数 $Y$，表示他们拥有的金币总数。

对于每个测试用例，输出形如 “Case #C: D” 的结果，其中 $C$ 是测试用例的编号（从 1 开始计），$D$ 是合法的定价组合数量。

- $1 \le T \le 100$ - $1 \le N \le 50$ - $1 \le X_i \le 10^9$ - $1 \le Y \le 10^{18}$ **本翻译由 AI 自动生成**