Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3682
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 ki 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.


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 ith integer is ki (1 ≤ i ≤ n). We promise that the sum of ki is equal to the sum of s1 and s2.The sum will modulo 1000000007.


In each test case, output the sum of ways.

Sample Input

2 1
2 1

Sample Output




Author: ZHOU, Xiao
Contest: ZOJ Monthly, January 2013
Submit    Status