The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 191 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

combinatorics

constructive algorithms

dp

meet-in-the-middle

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Axis Walking

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputIahub 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).

Input

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

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

Examples

Input

3

2 3 5

2

5 7

Output

1

Input

3

2 2 2

2

1 3

Output

6

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2024 04:52:11 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|