Codeforces Round 191 (Div. 2) |
---|
Закончено |
Яхуб хочет встретиться со своей подружкой Яхубиной. Они оба живут на оси 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, 4, 6], так что тут неудача не грозит Яхубу.
Название |
---|