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 的运气还算不错。