E. Идем по оси
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Яхуб хочет встретиться со своей подружкой Яхубиной. Они оба живут на оси Ox (горизонтальной оси координат). Яхуб живет в точке 0, а Яхубина живет в точке d.

У Яхуба есть n целых положительных чисел a1, a2, ..., an. Сумма этих чисел равняется d. Предположим, что p1, p2, ..., pn — это перестановка чисел {1, 2, ..., n}. Затем, пусть b1 = ap1, b2 = ap2 и так далее. Будем называть массив b — «путь». Существует n! различных путей, один путь для каждой перестановки p.

Яхуб запланировал поход к своей подружке следующим образом. Сначала он проходит b1 шагов по оси Ox, затем делает привал в точке b1. Затем он проходит еще b2 шагов по оси Ox и устраивает привал в точке b1 + b2. Аналогично, в j-ый раз (1 ≤ j ≤ n) он проходит еще bj шагов по оси Ox и делает привал в точке b1 + b2 + ... + bj.

Яхуб очень суеверный человек. У него есть k несчастливых целых чисел. Яхуб называет путь «хорошим», если он никогда не делает привала в точке, соответствующей хотя бы одному из этих k чисел. Просто из любопытства посчитайте, сколько существует хороших путей по модулю 1000000007 (109 + 7).

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 24). В следующей строке записано n целых чисел: a1, a2, ..., an (1 ≤ ai ≤ 109).

В третьей строке записано целое число k (0 ≤ k ≤ 2). В четвертой строке записано k положительных целых чисел, обозначающих несчастливые для Яхуба числа. Каждое из этих чисел не превышает 109.

Выходные данные

Выведите единственное целое число — ответ на дилемму Яхуба.

Примеры
Входные данные
3
2 3 5
2
5 7
Выходные данные
1
Входные данные
3
2 2 2
2
1 3
Выходные данные
6
Примечание

В первом тесте посмотрим на шесть возможных путей:

  • [2, 3, 5]. Яхуб остановится в точках 2, 5 и 10. Среди них несчастливое число — 5.
  • [2, 5, 3]. Яхуб остановится в точках 2, 7 и 10. Среди них несчастливое число — 7.
  • [3, 2, 5]. Остановка в несчастливой точке 5.
  • [3, 5, 2]. Такое расположение подходит.
  • [5, 2, 3]. Два несчастливых привала (5 и 7).
  • [5, 3, 2]. Яхуб не согласится, так как здесь есть привал в точке 5.

Во втором тесте заметьте, что два разных способа могут иметь идентичные наборы привалов. В конкретном случае, все шесть возможных способов имеют одни и те же остановки: [2, 4, 6], так что тут неудача не грозит Яхубу.