#1035. 命运

题目背景

与命运抗争，还是听从命运的安排。是一个选择。

题目描述

在阿太生活的那个渔村里，有一个神婆。神婆算命据说是很准的。

神婆算命的方法很简单。神婆会给你 张卡片和 个袋子，每张卡片上写着一个整数。然后神婆让你闭上眼睛选出卡片的一个子集，她会算出自己种的卡片上的数字的和，取绝对值之后给你同样数量的硬币。如果你能把这些硬币装入 个袋子，并使得袋子里的硬币数量都相同，她就会告诉你的命运。

为了计算你知道自己命运的概率，你首先要知道有多少不同的子集能让你通过神婆的考验。

注意，卡片都是不同的，即使两张卡片上写着一样的数字，它们也被认为是两张不同的卡片。

第一行有两个整数 和 。 表示要回答的询问数。

第二行有 个整数，表示写在各卡片上的数字。

接下来的 行，每行包含一个整数 。

输出能让你通过神婆的考验的不同子集的数量，答案对 取模。

样例 #1

样例输入 #1

5 1
1 2 -1 4 5
9

样例输出 #1

4

样例解释 #1

第一组询问：

能获胜的子集有 ，加和本别是

样例 #2

样例输入 #2

5 2
1 2 3 4 5
5
15

样例输出 #2

8
2

样例解释 #2

第一组询问:

能获胜的子集有

第二组询问:

能获胜的子集有

数据范围与约定

对于所有测试数据，保证:

• 卡片上的数字

子任务说明

后记

但是人，真的要被预言的命运所牵制吗？

灵感来源于：蔡崇达 《命运》