背景

高富帅的故事^_^

描述

FK要去找他的女朋友SY,他们处在同一条水平轴线上(x轴)。FK住在0点,SY住在d点。

FK有n张不同的行走卡片,卡片上的数字为 a1 , a2, ... , an。a1 + a2 + ... + an = d。当FK在点p时,使用第i张卡片,他就会直接瞬移到点p + ai

即使两张卡片上的数字相同,这两张卡片也被认为是不同的。因此,要想到达SY的家,显然FK有n!种不同的方法。

但是,追SY的男生不只FK一个。由于嫉妒,他们在路上放了k个陷阱,当FK踩到陷阱上时,他就会掉进去,也就见不到SY了。

问FK有多少种使用卡片的方案,使他不会掉进任何一个陷阱。

输入格式

第一行1个整数,n。

第二行n个整数,a1 , a2 , ... , an

第三行1个整数,k。

第四行k个整数,表示每个陷阱在x轴上的位置。

输出格式

输出1个整数,表示总方案数,将结果对 1000000007 (109 + 7) 取模。

样例输入

【样例输入1】

3

2 3 5

2

5 7

【样例输入2】

3

2 2 2

2

1 3

样例输出

【样例输出1】

1

【样例输出2】

6

数据范围与约定

1 ≤ n ≤ 24 0 ≤ k ≤ 2 1 ≤ ai ≤ 109

样例解释

【样例1】

2,3,5 FK会停在点2,5,10,在点5处有一个陷阱

2,5,3 FK会停在点2,7,10,在点7处有一个陷阱

3,2,5 FK会停在点5,7,10,在点5,7处各有一个陷阱

3,5,2 FK会停在点3,8,10,这是一种合法方案

5,2,3 FK会停在点5,7,10,在点5,7处各有一个陷阱

5,3,2 FK会停在点5,8,10,在点5处有一个陷阱

所以答案是1

【样例2】

无论FK怎么改变使用卡片的顺序,他都会停在点2,4,6,所以他不会踩到陷阱

所以答案是6

来源

CF