E - Cup 3
Time Limit: 3 Seconds
Memory Limit: 65536 KB
The 2012 Europe Cup was over and Spain won the Championship. The fans of Spain want to hold some activities to celebrate. But there is a question. Some of them are the fans of F.C Barcelona and the others are Real Madrid. It is well-known that the relation of these two clubs is very bad. So they may have some disharmony events when the fans of the two clubs celebrate together.
There are s1 fans of Barcelona and s2 fans of Madrid (0 ≤ s1, s2 ≤ 100000). The government provided n (2 ≤ n ≤ 200) squares and each square can contain k_{i} fans. Only if each square is all Barcelona's fans or Madrid's fans or the number of two clubs is equal exactly, it is harmony.
Your task is calculating the sum of ways that the celebration is harmony.
Input
There are multiple test cases(no more than 50). For each test case:
The first line contains two integers s1 and s2 (0 ≤ s1, s2 ≤ 100000), the number of fans of Barcelona and Madrid. The second line contains one integer n (2 ≤ n ≤ 200), the number of squares.
The third line contains n integers, the i_{th} integer is k_{i} (1 ≤ i ≤ n).
We promise that the sum of k_{i} is equal to the sum of s1 and s2.The sum will modulo 1000000007.
Output
In each test case, output the sum of ways.
Sample Input
2 1
2
2 1
Sample Output
2
Reference
http://en.wikipedia.org/wiki/FC_Barcelona
http://en.wikipedia.org/wiki/Real_Madrid
Author:
ZHOU, Xiao
Submit
Status