← 返回题目列表

Codeforces · 327/E

E. 轴行走

中文机器翻译题面 查看原题

Iahub 想见见他的女朋友 Iahubina。它们都位于 Ox 轴(水平轴)。 Iahub 位于点 0,Iahubina 位于点 d。

Iahub 有 n 个正整数 a1, a2, ..., an。这些数字的总和是 d。假设 p1, p2, ..., pn 是 {1, 2, ..., n} 的排列。然后,令 b1 = ap1,b2 = ap2 等等。数组b称为“路线”。有n个!不同的路线,每个排列 p 一条。

Iahub 的行程安排是:他在 Ox 轴上行走 b1 步,然后在 b1 点休息。然后,他在 Ox 轴上再走了 b2 步,并在点 b1 + b2 处突破。类似地,在第 j (1 ≤ j ≤ n) 次,他在 Ox 轴上多走了 bj 步,并在点 b1 + b2 + ... + bj 处休息。

Iahub 非常迷信,有 k 个整数,这给他带来了厄运。如果他从未在与这 k 个数字之一对应的点上中断,他就称一条路线为“好”。出于他自己的好奇心,回答他能走多少条好路线,模 1000000007 (109 + 7)。

输入

第一行包含一个整数 n (1 ≤ n ≤ 24)。下面一行包含 n 个整数:a1, a2, ..., an (1 ≤ ai ≤ 109)。

第三行包含整数 k (0 ≤ k ≤ 2)。第四行包含k个正整数,代表给Iahub带来霉运的数字。这些数字均不超过 109。

输出

输出一个整数——Iahub 困境模 1000000007 (109 + 7) 的答案。

示例

输入 #1

3
2 3 5
2
5 7

输出 #1

1

输入 #2

3
2 2 2
2
1 3

输出 #2

6

注意

在第一种情况下,考虑六种可能的顺序:

- [2、3、5]。 Iahub会停在2、5、10的位置。其中5对他来说是运气不好的。
- [2,5,3]。 Iahub会停在2、7、10的位置。其中7对他来说是霉运。
- [3,2,5]。他将停在不幸的 5 处。
- [3, 5, 2]。这是有效的订单。
- [5,2,3]。他倒霉了两次(5次和7次)。
- [5,3,2]。 Iahub 会拒绝,因为这会将他排到第 5 位。

在第二种情况下,请注意两种不同的方式可能具有相同的停止集。事实上,所有六种可能的方式都有相同的停靠点:[2,4,6],所以 Iahub 的运气还算不错。