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 java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.Map.Entry;

public class AxisWalkingMeetMiddle {
    static int MOD = 1000000007;
    static long[] fac;
    static int[] arr1;
    static int[] arr2;
    static Map<Key, Integer> left;
    static Map<Key, Integer> right;
    static int n;

    public static void main(String[] args) throws Exception {
        fac = new long[25];
        fac[0] = 1;
        for (int i = 1; i < fac.length; i++) {
            fac[i] = (fac[i - 1] * i) % MOD;
        }

        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        n = in.nextInt();
        arr1 = new int[Math.round(n / 2f)];
        arr2 = new int[n - arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = in.nextInt();
        }
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = in.nextInt();
        }

        int k = in.nextInt();
        int b1 = -1;
        int b2 = -1;
        if (k >= 1)
            b1 = in.nextInt();
        if (k == 2)
            b2 = in.nextInt();
        
        if(k != 0){
            // key = <sum,count> , val = # subsets with that sum,count
            left = new HashMap<Key, Integer>();
            right = new HashMap<Key, Integer>();

            Key[] leftKeys = new Key[1 << arr1.length];
            leftKeys[0] = new Key(0, 0);
            left.put(leftKeys[0], 1);
            for (int i = 0, mask = 1; i < arr1.length; i++, mask <<= 1) {
                leftKeys[mask] = new Key(1, arr1[i]);
            }
            for (int i = 1; i < (1 << arr1.length); i++) {
                int last = i & -i;
                int prev = i - last;
                leftKeys[i] = new Key(1 + leftKeys[prev].numChosen,
                        leftKeys[prev].sum + leftKeys[last].sum);
                Integer prevCount = left.get(leftKeys[i]);
                if (prevCount == null) {
                    prevCount = 0;
                }
                left.put(leftKeys[i], prevCount + 1);
            }

            Key[] rightKeys = new Key[1 << arr2.length];
            rightKeys[0] = new Key(0, 0);
            right.put(rightKeys[0], 1);
            for (int i = 0, mask = 1; i < arr2.length; i++, mask <<= 1) {
                rightKeys[mask] = new Key(1, arr2[i]);
            }
            rightKeys[0] = new Key(0, 0);
            for (int i = 1; i < (1 << arr2.length); i++) {
                int last = i & -i;
                int prev = i - last;
                rightKeys[i] = new Key(1 + rightKeys[prev].numChosen,
                        rightKeys[prev].sum + rightKeys[last].sum);
                Integer prevCount = right.get(rightKeys[i]);
                if (prevCount == null) {
                    prevCount = 0;
                }
                right.put(rightKeys[i], prevCount + 1);
            }
        }
        
        if (k == 0) {
            out.println(fac[n]);
        } else if (k == 1) {
            long ans = fac[n] - getNumPathTouch(b1);
            if (ans < 0)
                ans += MOD;
            out.println(ans);
        } else {
            long ans = fac[n];
            ans -= getNumPathTouch(b1);
            if (ans < 0)
                ans += MOD;
            ans -= getNumPathTouch(b2);
            if (ans < 0)
                ans += MOD;
            ans += getNumPathTouch(b1, b2);
            out.println(ans % MOD);
        }

        out.println();
        out.close();
    }

    // num paths touch b
    static long getNumPathTouch(int b) {
        long totalAns = 0;

        for (Entry<Key, Integer> leftEntry : left.entrySet()) {
            for (int rightCount = 0; rightCount <= arr2.length; rightCount++) {
                Integer numRightMatch = right.get(new Key(rightCount, b
                        - leftEntry.getKey().sum));
                if (numRightMatch != null) {
                    int totalBeforeTouch = leftEntry.getKey().numChosen
                            + rightCount;
                    long facCount = fac[totalBeforeTouch]
                            * fac[n - totalBeforeTouch] % MOD;
                    long subsetPairCount = (leftEntry.getValue() * numRightMatch)
                            % MOD;
                    totalAns = totalAns + (facCount * subsetPairCount) % MOD;
                    totalAns %= MOD;
                }
            }
        }
        return totalAns;
    }

    // return num path touches b1 and b2
    static long getNumPathTouch(int b1, int b2) {
        if (b1 > b2) {
            int temp = b1;
            b1 = b2;
            b2 = temp;
        }

        Map<Key, Map<Key, Integer>> leftTally = new HashMap<Key, Map<Key, Integer>>(10000000);
        Map<Key, Map<Key, Integer>> rightTally = new HashMap<Key, Map<Key, Integer>>(10000000);
        choose(0, new Key2(0,0,0,0), arr1, leftTally);
        choose(0, new Key2(0,0,0,0), arr2, rightTally);
        
        long ans = 0;
        
        for (Entry<Key, Map<Key, Integer>> firstLeftEntry : leftTally.entrySet()) {
            long needLeft = b1 - firstLeftEntry.getKey().sum;
            int countFirstLeft = firstLeftEntry.getKey().numChosen;
            if(needLeft < 0) continue;
            for (Entry<Key, Integer> firstMidEntry : firstLeftEntry.getValue().entrySet()) {
                long needMid = b2 - b1 - firstMidEntry.getKey().sum;
                int countFirstMid = firstMidEntry.getKey().numChosen;
                if(needMid < 0) continue;
                
                //now look at the other n/2 partition
                for (int leftCount = 0; leftCount <= arr2.length; leftCount++) {
                    Map<Key, Integer> secondRightTally = rightTally.get(new Key(leftCount, needLeft));
                    if(secondRightTally != null){
                        for (int midCount = 0; midCount <= arr2.length-leftCount; midCount++) {
                            Integer numRightMatch = secondRightTally.get(new Key(midCount, needMid));
                            if(numRightMatch != null){
                                int numLeft = countFirstLeft + leftCount;
                                int numMid = countFirstMid + midCount;
                                int numRight = n - numLeft - numMid;
                                long perm = ((fac[numLeft] * fac[numMid])%MOD * fac[numRight])%MOD;
                                long subsetPairCount = (firstMidEntry.getValue() * numRightMatch) % MOD;
                                ans = ans + (perm * subsetPairCount) % MOD;
                                ans %= MOD;
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
    
    static void choose(int toSet, Key2 curKey, int[] arr, Map<Key, Map<Key, Integer>> tally){
        if(toSet == arr.length){
            Key first = new Key(curKey.numLeftChosen, curKey.leftSum);
            Key second = new Key(curKey.numMidChosen, curKey.midSum);
            Map<Key, Integer> midTally = tally.get(first);
            if(midTally == null){
                midTally = new HashMap<Key, Integer>();
                tally.put(first, midTally);
            }
            Integer prevCount = midTally.get(second);
            if(prevCount == null){
                prevCount = 0;
            }
            
            midTally.put(second, prevCount+1);
        }else{
            //either left, mid, or right
            //left
            curKey.leftSum += arr[toSet];
            curKey.numLeftChosen++;
            choose(toSet+1, curKey, arr, tally);
            curKey.leftSum -= arr[toSet];
            curKey.numLeftChosen--;
            
            //mid
            curKey.midSum += arr[toSet];
            curKey.numMidChosen++;
            choose(toSet+1, curKey, arr, tally);
            curKey.midSum -= arr[toSet];
            curKey.numMidChosen--;
            
            //right
            choose(toSet+1, curKey, arr, tally);
        }
    }
    
    static class Key2 {
        public Key2 copy(){
            return new Key2(leftSum, midSum, numLeftChosen, numMidChosen);
        }
        
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + (int) leftSum;
            result = prime * result + (int) midSum;
            result = prime * result + numLeftChosen;
            result = prime * result + numMidChosen;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            Key2 other = (Key2) obj;
            if (leftSum != other.leftSum)
                return false;
            if (midSum != other.midSum)
                return false;
            if (numLeftChosen != other.numLeftChosen)
                return false;
            if (numMidChosen != other.numMidChosen)
                return false;
            return true;
        }

        public long leftSum;
        public long midSum;
        public int numLeftChosen;
        public int numMidChosen;

        public Key2(long leftSum, long midSum, int numLeftChosen,
                int numMidChosen) {
            this.leftSum = leftSum;
            this.midSum = midSum;
            this.numLeftChosen = numLeftChosen;
            this.numMidChosen = numMidChosen;
        }
    }

    static class Key {
        public int numChosen;
        public long sum;

        public Key(int numChosen, long sum) {
            this.numChosen = numChosen;
            this.sum = sum;
        }

        @Override
        public boolean equals(Object other) {
            Key o = (Key) other;
            return this.numChosen == o.numChosen && this.sum == o.sum;
        }

        @Override
        public int hashCode() {
            return 31 * numChosen + (int) sum;
        }
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String nextToken() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

}