Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Яхуб хочет встретиться со своей подружкой Яхубиной. Они оба живут на оси 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], так что тут неудача не грозит Яхубу.