Axis Walking

题意翻译

给你一个长度为$n(1<=n<=24)$的正整数序列$S$，再有$k(0<=k<=2)$个正整数。 求有多少种$S$的排列方式使得其前缀和不会成为那$k$个数里的任意一个。 答案对$1e9+7$取模。

题目描述

Iahub wants to meet his girlfriend Iahubina. They both live in $ Ox $ axis (the horizontal axis). Iahub lives at point 0 and Iahubina at point $ d $ . Iahub has $ n $ positive integers $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ . The sum of those numbers is $ d $ . Suppose $ p_{1} $ , $ p_{2} $ , ..., $ p_{n} $ is a permutation of $ {1,2,...,n} $ . Then, let $ b_{1}=a_{p1} $ , $ b_{2}=a_{p2} $ and so on. The array b is called a "route". There are $ n! $ different routes, one for each permutation $ p $ . Iahub's travel schedule is: he walks $ b_{1} $ steps on $ Ox $ axis, then he makes a break in point $ b_{1} $ . Then, he walks $ b_{2} $ more steps on $ Ox $ axis and makes a break in point $ b_{1}+b_{2} $ . Similarly, at $ j $ -th $ (1<=j<=n) $ time he walks $ b_{j} $ more steps on $ Ox $ axis and makes a break in point $ b_{1}+b_{2}+...+b_{j} $ . Iahub is very superstitious and has $ k $ integers which give him bad luck. He calls a route "good" if he never makes a break in a point corresponding to one of those $ k $ numbers. For his own curiosity, answer how many good routes he can make, modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 1<=n<=24 $ ). The following line contains $ n $ integers: $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ). The third line contains integer $ k $ ( $ 0<=k<=2 $ ). The fourth line contains $ k $ positive integers, representing the numbers that give Iahub bad luck. Each of these numbers does not exceed $ 10^{9} $ .

输出格式

Output a single integer — the answer of Iahub's dilemma modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).

输入输出样例

输入样例 #1

3
2 3 5
2
5 7

输出样例 #1

1

输入样例 #2

3
2 2 2
2
1 3

输出样例 #2

6

说明

In the first case consider six possible orderings: - \[2, 3, 5\]. Iahub will stop at position 2, 5 and 10. Among them, 5 is bad luck for him. - \[2, 5, 3\]. Iahub will stop at position 2, 7 and 10. Among them, 7 is bad luck for him. - \[3, 2, 5\]. He will stop at the unlucky 5. - \[3, 5, 2\]. This is a valid ordering. - \[5, 2, 3\]. He got unlucky twice (5 and 7). - \[5, 3, 2\]. Iahub would reject, as it sends him to position 5. In the second case, note that it is possible that two different ways have the identical set of stopping. In fact, all six possible ways have the same stops: \[2, 4, 6\], so there's no bad luck for Iahub.