Axis Walking

3000ms

524288K

Description:

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₁, a₂, ..., a_n. The sum of those numbers is d. Suppose p₁, p₂, ..., p_n is a permutation of {1, 2, ..., n}. Then, let b₁ = a_p₁, b₂ = a_p₂ 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₁ steps on Ox axis, then he makes a break in point b₁. Then, he walks b₂ more steps on Ox axis and makes a break in point b₁ + b₂. Similarly, at j-th (1 ≤ j ≤ n) time he walks b_j more steps on Ox axis and makes a break in point b₁ + b₂ + ... + 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⁹ + 7).

Input:

The first line contains an integer n (1 ≤ n ≤ 24). The following line contains n integers: a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

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⁹.

Output:

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

Sample Input:

Sample Output:

Sample Input:

Sample Output:

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.

Informação

Provedor Codeforces

Código CF327E