A9145 | 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_{p1}$ , $b_{2}=a_{p2}$ 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$ ( $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}<=10^{9}$ ).

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 $10^{9}$ .

Output a single integer — the answer of Iahub's dilemma modulo $1000000007$ ( $10^{9}+7$ ).