CF327E.Axis Walking

Iahub wants to meet his girlfriend Iahubina. They both live in Ox axis (the horizontal axis). Iahub lives at point 0 and Iahubina at point d.

Iahub has n positive integers _a_1, _a_2, ..., a__n. The sum of those numbers is d. Suppose _p_1, _p_2, ..., p__n is a permutation of {1, 2, ..., n}. Then, let _b_1 = _a__p_1, _b_2 = _a__p_2 and so on. The array b is called a "route". There are n! different routes, one for each permutation p.

Iahub's travel schedule is: he walks _b_1 steps on Ox axis, then he makes a break in point _b_1. Then, he walks _b_2 more steps on Ox axis and makes a break in point _b_1 + _b_2. Similarly, at j-th (1 ≤ j ≤ n) time he walks b__j more steps on Ox axis and makes a break in point _b_1 + _b_2 + ... + b__j.

Iahub is very superstitious and has k integers which give him bad luck. He calls a route "good" if he never makes a break in a point corresponding to one of those k numbers. For his own curiosity, answer how many good routes he can make, modulo 1000000007 (109 + 7).

Iahub 想要与他的女友 Iahubina 相会。他们俩都住在 $Ox$ 轴（即水平轴）上。Iahub 住在坐标 $0$ 处，而 Iahubina 住在坐标 $d$ 处。

Iahub 有 $n$ 个正整数 $a_1, a_2, \dots, a_n$，它们的和为 $d$。设 $p_1, p_2, \dots, p_n$ 是集合 $\{1,\,2,\,\dots,\,n\}$ 的一个排列。定义 $b_1 = a_{p_1},\, b_2 = a_{p_2},\, \dots$。数组 $b$ 被称为一条“路径”。共有 $n!$ 条不同的路径，每条对应一个排列 $p$。

Iahub 的行程安排如下：他先在 $Ox$ 轴上行走 $b_1$ 步，并在位置 $b_1$ 处休息；接着再行走 $b_2$ 步，并在位置 $b_1 + b_2$ 处休息；依此类推，在第 $j$ 次（其中 $1 \le j \le n$）行走时，他再走 $b_j$ 步，并在位置 $b_1 + b_2 + \dots + b_j$ 处休息。

Iahub 非常迷信，他有 $k$ 个会给他带来厄运的整数。若一条路径中，Iahub 在任意一次休息时所处的位置均不等于这 $k$ 个厄运整数中的任何一个，则称该路径为“好路径”。出于好奇，请你计算他总共能构造出多少条好路径，结果对 $1000000007$（即 $10^9 + 7$）取模。

The first line contains an integer n (1 ≤ n ≤ 24). The following line contains n integers: _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).

The third line contains integer k (0 ≤ k ≤ 2). The fourth line contains k positive integers, representing the numbers that give Iahub bad luck. Each of these numbers does not exceed 109.

第一行包含一个整数 $n$（$1 \leq n \leq 24$）。第二行包含 $n$ 个整数：$a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i \leq 10^9$）。

第三行包含一个整数 $k$（$0 \leq k \leq 2$）。第四行包含 $k$ 个正整数，表示给 Iahub 带来厄运的数字。这些数字均不超过 $10^9$。

Output a single integer — the answer of Iahub's dilemma modulo 1000000007 (109 + 7).

输出一个整数——Iahub 难题的答案对 1000000007（$10^9 + 7$）取模的结果。

In the first case consider six possible orderings:

• [2, 3, 5]. Iahub will stop at position 2, 5 and 10. Among them, 5 is bad luck for him.
• [2, 5, 3]. Iahub will stop at position 2, 7 and 10. Among them, 7 is bad luck for him.
• [3, 2, 5]. He will stop at the unlucky 5.
• [3, 5, 2]. This is a valid ordering.
• [5, 2, 3]. He got unlucky twice (5 and 7).
• [5, 3, 2]. Iahub would reject, as it sends him to position 5.

In the second case, note that it is possible that two different ways have the identical set of stopping. In fact, all six possible ways have the same stops: [2, 4, 6], so there's no bad luck for Iahub.

第一种情况考虑六种可能的排列顺序：

• [2, 3, 5]。Iahub 将停在位置 2、5 和 10。其中，5 对他而言是不吉利的。
• [2, 5, 3]。Iahub 将停在位置 2、7 和 10。其中，7 对他而言是不吉利的。
• [3, 2, 5]。他将停在不吉利的位置 5。
• [3, 5, 2]。这是一个合法的排列顺序。
• [5, 2, 3]。他遭遇了两次不吉利（5 和 7）。
• [5, 3, 2]。Iahub 会拒绝该排列，因为它会将他送到位置 5。

第二种情况下，请注意：两种不同的排列方式可能具有完全相同的停靠位置集合。事实上，全部六种可能的排列方式均产生相同的停靠位置：[2, 4, 6]，因此 Iahub 不会遇到任何不吉利的情况。