Problem: 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 a1, a2, ..., an. The sum of those numbers is d. Suppose p1, p2, ..., pn is a permutation of {1, 2, ..., n}. Then, let b1 = ap1, b2 = ap2 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 b1 steps on Ox axis, then he makes a break in point b1. Then, he walks b2 more steps on Ox axis and makes a break in point b1 + b2. Similarly, at j-th (1 ≤ j ≤ n) time he walks bj more steps on Ox axis and makes a break in point b1 + b2 + ... + bj.

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

Input

The first line contains an integer n (1 ≤ n ≤ 24). The following line contains n integers: a1, a2, ..., an (1 ≤ ai ≤ 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.

Output

Output a single integer — the answer of Iahub's dilemma modulo 1000000007 (109 + 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.

Solution (in JAVA):

Solution:
import static java.util.Arrays.deepToString;
import static java.util.Arrays.sort;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Comparator;
import java.util.Properties;
import java.util.StringTokenizer;

public class Main {

	final long MOD = 1000000007;

	long fact[] = new long[30];

	void solve() {
		int n = sc.nextInt();
		int[] a = sc.nextIntArray(n);
		sort(a);

		int k = sc.nextInt();
		int[] ks = sc.nextIntArray(k);
		sort(ks);

		fact[0] = 1;
		for (int i = 1; i < 30; i++) fact[i] = fact[i-1] * i % MOD;


		if (k == 0) {
			out.println(fact[n]);
			return;
		}
		if (k == 1) {
			long ans = fact[n];
			long sub = make(a, ks[0]);
			ans = (ans + MOD - sub) % MOD;
			out.println(ans);
			return;
		}

		if (k == 2) {
			long ans = fact[n];
			{
				long sub = make(a, ks[1]);
				tr(sub);
				ans = (ans + MOD - sub) % MOD;
			}
			{
				long sub = make(a, ks[0]);
				tr(sub);
				ans = (ans + MOD - sub) % MOD;
			}

			{
				long sub = make2(a, ks[0], ks[1] - ks[0]);
				tr(sub);
				ans = (ans + sub) % MOD;
			}
			out.println(ans);
		}


	}


	long make(int[] a, int k) {
		int n = a.length;

		int m1 = (n+1) / 2;
		int m2 = (n) / 2;

		int[][] b1 = new int[1 << m1][2];
		int[][] b2 = new int[1 << m2][2];

		for (int set = 0; set < b1.length; set++) {
			long s = 0;
			int on = 0;
			for (int i = 0; i < m1; i++) if ((set >> i & 1) == 1) {
				s += a[i];
				++on;
			}
			b1[set][0] = s <= k ? (int)s : k + 1 ;
			b1[set][1] = on;
		}

		for (int set = 0; set < b2.length; set++) {
			long s = 0;
			int on = 0;
			for (int i = 0; i < m2; i++) if ((set >> i & 1) == 1) {
				s += a[m1 + i];
				++on;
			}
			b2[set][0] = s <= k ? (int)s : k + 1 ;
			b2[set][1] = on;
		}
		sort(b1, new Comparator<int[]>(){
			public int compare(int[] a, int[] b){
				return a[0] - b[0];
			}
		});
		sort(b2, new Comparator<int[]>(){
			public int compare(int[] a, int[] b){
				return a[0] - b[0];
			}
		});


		long res = 0;

		for (int i = 0; i < b1.length; i++) {
			int x = b1[i][0];

			int t = k - x;
			if (t < 0) {
				continue;
			}
			int lb = lower_bound(b2, t);
			int ub = upper_bound(b2, t);
			for (int p = lb; p < ub; p++) {
				int bit = b1[i][1] + b2[p][1];
				res += fact[bit] * fact[n - bit] % MOD;
				res %= MOD;
			}
		}
		return res;
	}

	int lower_bound(int[][] a, int val) {
		int lo = -1;
		int hi = a.length;
		while (hi - lo > 1) {
			int mid = (hi + lo) >> 1;
			if (a[mid][0] < val) lo = mid; else hi = mid;
		}
		return hi;
	}

	int upper_bound(int[][] a, int val) {
		int lo = -1;
		int hi = a.length;
		while (hi - lo > 1) {
			int mid = (hi + lo) >> 1;
			if (a[mid][0] <= val) lo = mid; else hi = mid;
		}
		return hi;
	}


	class Tupple implements Comparable<Tupple> {
		int v1, c1;
		int v2, c2;

		public int compareTo(Tupple o) {
			if (v1 != o.v1) return v1 < o.v1 ? -1 : 1;
			if (v2 != o.v2) return v2 < o.v2 ? -1 : 1;
			return 0;
		}

		public Tupple(int v1, int c1, int v2, int c2) {
			this.v1 = v1;
			this.c1 = c1;
			this.v2 = v2;
			this.c2 = c2;
		}
	}

	long make2(int [] a, int k1, int k2) {

		final int big = 1001001001;

		int n = a.length;

		int m1 = (n) / 2;
		int m2 = (n+1) / 2;
		Tupple[] b1 = new Tupple[(int)Math.pow(3, m1)];
		Tupple[] b2 = new Tupple[(int)Math.pow(3, m2)];

		for (int set = 0; set < b1.length; set++) {
			int t = set;
			long v1 = 0, c1 = 0, v2 = 0, c2 = 0;
			for (int i = 0; i < m1; i++) {
				switch(t % 3) {
				case 0: { v1 += a[i]; c1++; } break;
				case 1: { v2 += a[i]; c2++; } break;
				case 2:break;
				}
				t /= 3;
			}
			b1[set] = new Tupple((int)Math.min(v1, big), (int)c1, (int)Math.min(v2, big), (int)c2);
		}

		for (int set = 0; set < b2.length; set++) {
			int t = set;
			long v1 = 0, c1 = 0, v2 = 0, c2 = 0;
			for (int i = 0; i < m2; i++) {
				switch(t % 3) {
				case 0: { v1 += a[m1 + i]; c1++; } break;
				case 1: { v2 += a[m1 + i]; c2++; } break;
				case 2:break;
				}
				t /= 3;
			}
			b2[set] = new Tupple((int)Math.min(v1, big), (int)c1, (int)Math.min(v2, big), (int)c2);
		}
		sort(b1);
		sort(b2);

//		tr(b1.length);
//		tr(b2.length);

		long res = 0;

		Tupple t = new Tupple(0,0,0,0);

		Tupple px1 = null;
		long gain = 0;

		for (Tupple x1 : b1) {

			t.v1 = k1 - x1.v1;
			t.v2 = k2 - x1.v2;
			if (t.v1 < 0 || t.v2 < 0) continue;

			if (px1 != null && px1.compareTo(x1) == 0 && x1.c1 == px1.c1 && x1.c2 == px1.c2) {
				res = (res + gain) % MOD;
				continue;
			}

			px1 = x1;


			int lb = lower_bound(b2, t);
			int ub = upper_bound(b2, t);

			gain = 0;
			for (int p = lb; p < ub; p++) {
				Tupple x2 = b2[p];
				int bit1 = x1.c1 + x2.c1;
				int bit2 = x1.c2 + x2.c2;
				gain += fact[bit1] * fact[bit2] % MOD * fact[n - bit1 - bit2] % MOD;
				if (gain >= MOD) gain -= MOD;
			}
			gain %= MOD;
			res = (res + gain) % MOD;
		}
		return res;
	}


	int lower_bound(Tupple[] a, Tupple val) {
		int lo = -1;
		int hi = a.length;
		while (hi - lo > 1) {
			int mid = (hi + lo) >> 1;
			if (a[mid].compareTo(val) < 0) lo = mid; else hi = mid;
		}
		return hi;
	}

	int upper_bound(Tupple[] a, Tupple val) {
		int lo = -1;
		int hi = a.length;
		while (hi - lo > 1) {
			int mid = (hi + lo) >> 1;
			if (a[mid].compareTo(val) <= 0) lo = mid; else hi = mid;
		}
		return hi;
	}
	public static void main(String[] args) throws Exception {
		Class<?> here = new Object(){}.getClass().getEnclosingClass();
		try {
			String packageName = here.getPackage().getName();
			packageName = "src/" + packageName.replaceAll("\\.", "/") + "/";
			System.setIn(new FileInputStream(packageName + "input.txt"));
//			System.setOut(new PrintStream(new FileOutputStream(packageName + "output.txt")));
		} catch (FileNotFoundException e) {
		} catch (NullPointerException e) {
		}

		Object o = Class.forName(here.getName()).newInstance();
		o.getClass().getMethod("run").invoke(o);
	}

	static void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	void print(int[] a) {
		out.print(a[0]);
		for (int i = 1; i < a.length; i++) out.print(" " + a[i]);
		out.println();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}