One day, Wet Shark was given an array $X=\{x_1,x_2,\ldots,x_m\}$. As always, he started playing with its subsequences. 

When you came to know about this habit, you presented him a task of finding all pairs of subsequences, $(A,B)$, which satisfies all of the following constraints. We will represent a pair of subsequence as $A=\{x_{a_1},x_{a_2},...,x_{a_n}\}$ and $B=\{x_{b_1},x_{b_2},...,x_{b_n}\}$ 

$\mbox{A}$ and $\mbox{B}$ must be of same length, i.e., $|A|=|B|$.
$\sum\limits_{i=1}^{n}(x_{a_{i}}+x_{b_{i}})=r$
$\sum\limits_{i=1}^{n}(x_{a_{i}}-x_{b_{i}})=s$

Please help Wet Shark determine how many possible subsequences $\mbox{A}$ and $\mbox{B}$ can exist. Because the number of choices may be big, output your answer modulo $10^9+7=1000000007$. 

Note: 

Two segments are different if there's exists at least one index $\boldsymbol{i}$ such that element $x_i$ is present in exactly one of them.
Both subsequences can overlap each other.
Subsequences do not necessarily have to be distinct

Input Format

The first line consists of 3 space-separated integers $m$, $\textbf{r}$, $\boldsymbol{\mathrm{~S~}}$, where $m$ denotes the length of the original array, $\mbox{X}$, and $\textbf{r}$ and $\boldsymbol{\mathrm{~S~}}$ are as defined above. 

The next line contains $m$ space-separated integers, $x_1,x_2,\ldots,x_m$ , representing the elements of $\mbox{X}$.

Constraints

$1\leq m\leq100$  
$0\leq r,\:\textit{s}\leq2000$  
$1\leq x_i\leq2000$  

Output Format

Output total number of pairs of subsequences, $(A,B)$, satisfying the above conditions. As the number can be large, output it's modulo $10^9+7=1000000007$

Sample Input 0
4 5 3
1 1 1 4

Sample Output 0
3

Explanation 0

For array $X=\{x_1,x_2,x_3,x_4\}=\{1,1,1,4\}$ there are three pairs of subsequences: 

$A=\{x_4\}=\{4\};B=\{x_1\}=\{1\}$
$A=\{x_4\}=\{4\};B=\{x_2\}=\{1\}$
$A=\{x_4\}=\{4\};B=\{x_3\}=\{1\}$

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


modu = int(1000000000.0 + 7)
d_prev = []
d_at = []

def merge(d1, d2):
	ret = d1.copy()
	ret.update(d2)
	keys_d1 = set(d1.keys())
	keys_d2 = set(d2.keys())
	for k in keys_d1 & keys_d2:
		ret[k] += d1[k]
	return ret

def do_len(l, s_a, s_b):
	cnt_a = 0
	cnt_b = 0
	g_a = True
	g_b = True
	do_len.done = False
	top = m - l
	for i in range(0, top):
		d_at[i].clear()
		for (k, v) in d_prev[i + 1].items():
			new_key = k + X[i]
			if new_key == s_a:
				cnt_a += v
				cnt_a %= modu
			if new_key == s_b:
				cnt_b += v
				cnt_b %= modu
			if new_key < s_a:
				g_a = False
				d_at[i][new_key] = v % modu
			if new_key < s_b:
				g_b = False
				d_at[i][new_key] = v % modu
	if g_a and g_b:
		do_len.done = True
	if l != m and (not do_len.done):
		d_prev[top - 1] = d_at[top - 1]
		for i in range(top - 2, -1, -1):
			d_prev[i] = merge(d_prev[i + 1], d_at[i])
	return cnt_a * cnt_b % modu
do_len.done = True

def answer():
	rps = r + s
	rms = r - s
	if rps <= 0 or rms <= 0 or rps % 2 == 1 or (rms % 2 == 1):
		return 0
	s_a = rps // 2
	s_b = rms // 2
	cnt = 0
	for l in range(0, m):
		cnt += do_len(l, s_a, s_b)
		cnt %= modu
		if do_len.done:
			break
	return cnt
(m, r, s) = map(int, input().split())
X = list(map(int, input().split()))
for i in range(0, m + 1):
	d_prev.append({0: 1})
	d_at.append({})
print(answer())


import sys
M = 10 ** 9 + 7
(m, r, s) = (int(x) for x in str(input()).split())
if r < s:
	print(0)
	sys.exit()
(a, b) = ((r + s) // 2, (r - s) // 2)
arr = [int(x) for x in str(input()).split()]
dp = [[0 for _ in range(2001)] for _ in range(m)]
for i in range(m):
	for j in range(i - 1, -1, -1):
		for k in range(2001):
			if k + arr[i] >= 2001:
				break
			dp[j + 1][k + arr[i]] += dp[j][k]
	dp[0][arr[i]] += 1
ans = 0
for i in range(m):
	ans = (ans + dp[i][a] * dp[i][b] % M) % M
print(ans)


(m, r, s) = map(int, input().split())
xs = map(int, input().split())
sums = {0: {0: 1}}
for x in xs:
	for key in reversed(sorted(sums.keys())):
		if x + key > (r + s) // 2:
			continue
		items = sums[key]
		for item in items:
			numbers = items[item]
			new_items = sums.setdefault(x + key, {})
			new_items.setdefault(item + 1, 0)
			new_items[item + 1] += numbers
res = 0
items = sums.setdefault((r + s) // 2, {})
for length in items:
	res += items[length] * sums.setdefault((r - s) // 2, {}).setdefault(length, 0)
print(0 if r + s == 0 else res % (10 ** 9 + 7))


from collections import defaultdict
MOD_BASE = pow(10, 9) + 7

def solve(x, r, s):
	if r % 2 != s % 2 or r <= s:
		return 0
	sums = []
	for (i, n) in enumerate(x):
		if len(sums) == 0 or len(sums[-1]) != 0:
			sums.append(defaultdict(int))
		for j in reversed(range(0, len(sums) - 1)):
			for (k, v) in sums[j].items():
				if k + n <= r:
					sums[j + 1][k + n] += v
		sums[0][n] += 1
	result = 0
	sa = (r + s) // 2
	sb = (r - s) // 2
	for sm in sums:
		if sa not in sm or sb not in sm:
			continue
		na = sm[sa]
		nb = sm[sb]
		cur = na * nb
		result = (result + cur) % MOD_BASE
	return result
(n, r, s) = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
print(solve(x, r, s))


import sys
(M, R, S) = tuple(map(int, input().split()))
X = tuple(map(int, input().split()))
if R < S:
	print(0)
	sys.exit()
if R + S % 2 == 1:
	print(0)
	sys.exit()
DP_Limit = (R + S) // 2
DP = [[0] * (DP_Limit + 1) for _ in range(M + 1)]
DP[0][0] = 1
for i in range(M):
	for l in range(M, 0, -1):
		for s in range(DP_Limit + 1):
			if s >= X[i]:
				DP[l][s] += DP[l - 1][s - X[i]]
res = 0
sa = (R + S) // 2
sb = (R - S) // 2
for i in range(1, M + 1):
	res += DP[i][sa] * DP[i][sb]
print(res % 1000000007)


import math
mod = 10 ** 9 + 7

def solve():
	(m, r, s) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	print(number_of_subsequence_pairs(arr, r, s))

def number_of_subsequence_pairs(arr, r, s):
	target1 = r + s
	target2 = r - s
	m = len(arr)
	arr.insert(0, 0)
	memo = [[{} for j in range(m + 1)] for i in range(m + 1)]
	for j in range(1, m + 1):
		for i in range(j, m + 1):
			s_range = range(1, target1 + 1) if j == 1 else range(min(memo[i][j - 1]), target1 + 1) if len(memo[i][j - 1]) > 0 else range(0)
			for s in s_range:
				if j == 1:
					if s == arr[i] * 2:
						count = 1 + get_num_subsequences(i - 1, j, s, memo)
					else:
						count = get_num_subsequences(i - 1, j, s, memo)
				else:
					count = get_num_subsequences(i - 1, j - 1, s - arr[i] * 2, memo) + get_num_subsequences(i - 1, j, s, memo)
				if count != 0:
					memo[i][j][s] = count
	return combine_subsequence_pairs(target1, target2, memo, m)

def get_num_subsequences(i, j, s, memo):
	if i == 0 or j == 0 or s <= 0 or (s not in memo[i][j]):
		return 0
	else:
		return memo[i][j][s]

def combine_subsequence_pairs(target1, target2, memo, m):
	result = 0
	for j in range(1, m + 1):
		result += memo[m][j].get(target1, 0) * memo[m][j].get(target2, 0) % mod
		result %= mod
	return result
solve()


def main():
	MOD = 10 ** 9 + 7
	(m, r, s) = list(map(int, input().strip().split(' ')))
	X = list(map(int, input().strip().split(' ')))
	X = [0] + X
	A = [[[0 for k in range(2001)] for j in range(m + 1)] for i in range(m + 1)]
	for i in range(1, m + 1):
		if i == 1:
			A[1][1][X[1]] = 1
		else:
			for j in range(1, i):
				for k in range(2001):
					temp = A[i - 1][j][k]
					A[i][j][k] = temp
			x = X[i]
			A[i][1][x] += 1
			A[i][1][x] %= MOD
			for j in range(2, i + 1):
				for k in range(1, 2000 - x + 1):
					temp = A[i - 1][j - 1][k]
					A[i][j][x + k] += temp
					A[i][j][x + k] %= MOD
	check = 0
	if (r + s) % 2 == 0 and (r - s) % 2 == 0 and (r >= s):
		check = 1
		w1 = (r + s) // 2
		w2 = (r - s) // 2
	if check == 0:
		print(0)
	else:
		ans = 0
		for L in range(1, m + 1):
			ans += A[m][L][w1] * A[m][L][w2]
			ans %= MOD
		print(ans)
main()


import sys
line1 = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
(n, r, s) = (line1[0], line1[1], line1[2])
MOD = 1000000007

def total_subseqs(X, n, r, s):
	if (r - s) % 2 == 1 or r <= s:
		return sys.stdout.write(str(0))
	if r == 0 and s == 0:
		return sys.stdout.write(str(0))
	S = int((r + s) / 2)
	DP = [[0 for x in range(0, len(X) + 1)] for y in range(0, S + 1)]
	DP[0][0] = 1
	sum_A = int((r + s) / 2)
	sum_B = int((r - s) / 2)
	total = 0
	A = 0
	B = 0
	compute_DP_s_j(DP, sum_A, n, X)
	for i in range(1, n + 1):
		A = DP[sum_A][i]
		B = DP[sum_B][i]
		total += int(A * B % MOD)
	total %= MOD
	return sys.stdout.write(str(total))

def compute_DP_s_j(DP, s, j, X):
	for i in range(0, len(X)):
		for sum_ in range(s, -1, -1):
			if X[i] + sum_ > s:
				continue
			for j_ in range(0, len(X)):
				DP[sum_ + X[i]][j_ + 1] += DP[sum_][j_]
				DP[sum_ + X[i]][j_ + 1] %= MOD
	return DP
total = total_subseqs(X, n, r, s)


from collections import Counter
MOD = 1000000007

def get_sums(seq, r, s):
	if (r + s) % 2 != 0:
		return 0
	if s > r:
		return 0
	a = (r + s) // 2
	b = r - a
	counts = [Counter()]
	for i in seq:
		counts.append(Counter())
		sub_length = len(counts) - 1
		while sub_length >= 2:
			current = counts[sub_length]
			prev = counts[sub_length - 1]
			for c in prev:
				if c + i <= r:
					current[c + i] += prev[c]
			sub_length -= 1
		counts[1][i] += 1
	total = 0
	for totals in counts:
		total += totals[a] * totals[b]
	return total
(count, r, s) = map(int, input().strip().split())
seq = map(int, input().strip().split())
print(get_sums(seq, r, s) % MOD)


MOD = 1000000007
from collections import defaultdict
(m, r, s) = map(int, input().split())
xi = list(map(int, input().split()))

def get_nseq(xi, vals):
	maxval = max(vals)
	cnt = defaultdict(lambda : 0, {(0, 0): 1})
	for x in xi:
		newcnt = cnt.copy()
		for (vl, w) in cnt.items():
			(v, l) = vl
			newv = v + x
			if newv > maxval:
				continue
			newl = l + 1
			newcnt[newv, newl] += w
		cnt = newcnt
	return [{l: w for ((v, l), w) in cnt.items() if v == val} for val in vals]

def solve(xi, r, s):
	if r + s & 1 != 0:
		return 0
	suma = (r - s) // 2
	sumb = (r + s) // 2
	(nas, nbs) = get_nseq(xi, [suma, sumb])
	retv = 0
	for (l, w) in nas.items():
		if l == 0:
			continue
		if not l in nbs:
			continue
		w2 = nbs[l]
		retv = (retv + w * w2) % MOD
	return retv
print(solve(xi, r, s))


import os
import sys
from copy import copy, deepcopy
MOD = 10 ** 9 + 7
M_2 = 500000004

def twoSubsequences(n, r, s, ip):
	if r == 0:
		return 0
	if (r + s) % 2 == 1:
		return 0
	if s > r:
		return 0
	if (r - s) % 2 == 1:
		return 0
	m1 = (r + s) // 2
	m2 = (r - s) // 2
	ip = [a for a in ip if a <= m1]
	ip.sort()
	n = len(ip)
	sums = [[0 for _ in range(n + 1)] for i in range(m1 + 1)]
	for a in ip:
		old_sums = deepcopy(sums)
		new_i = [x for x in range(1, m1 - a + 1) if sums[x][0] == 1]
		for i in new_i:
			j = i + a
			sums[j][0] = 1
			for k in range(1, n):
				sums[j][k + 1] = (sums[j][k + 1] + old_sums[i][k]) % MOD
		sums[a][0] = 1
		sums[a][1] += 1
	res = 0
	if s == 0:
		if sums[m1][0]:
			for i in range(1, n + 1):
				if sums[m1][i] >= 2:
					new_res = sums[m1][i] * sums[m1][i] % MOD
					res += new_res
					res = res % MOD
	elif sums[m1][0] and sums[m2][0]:
		for i in range(1, n + 1):
			res += sums[m1][i] * sums[m2][i]
			res = res % MOD
	return res
(n, r, s) = map(int, input().split())
ip = list(map(int, input().split()))
res = twoSubsequences(n, r, s, ip)
print(res)


from collections import Counter

def solve(x, r, s):
	if r <= s or (r ^ s) & 1:
		return 0
	m = 1000000007
	c = Counter([(0, 0)])
	(t, u) = ((r + s) // 2, (r - s) // 2)
	w = [0] * (1 + t)
	w[0] = 1
	for z in x:
		d = Counter()
		for (i, y) in c:
			if z + y <= t:
				d[i + 1, z + y] = c[i, y]
		for (i, y) in d:
			c[i, y] = (c[i, y] + d[i, y]) % m
	total = 0
	for i in range(1, 1 + len(x)):
		total = (total + c[i, t] * c[i, u]) % m
	return total
(_, r, s) = map(int, input().split())
x = list(map(int, input().split()))
print(solve(x, r, s))


(m, r, s) = map(int, input().split(' '))
(D, M) = ([int(x) for x in input().split(' ')], 10 ** 9 + 7)
if (r ^ s) & 1 or s > r:
	print(0)
else:
	(a, b) = (r + s >> 1, r - s >> 1)
	a1 = a + 1
	(A, B) = ([[0] * a1 for _ in range(100)], [[0] * a1 for _ in range(100)])
	for i in range(1, m + 1):
		x = D[i - 1]
		for p in range(1, i):
			for q in range(a1):
				B[p - 1][q] = A[p - 1][q]
		for q in range(a1):
			B[i - 1][q] = 0
		if x < a1:
			B[0][x] += 1
		for p in range(1, i):
			for q in range(a - x + 1):
				B[p][q + x] = (B[p][q + x] + A[p - 1][q]) % M
		(A, B) = (B, A)
	rs = 0
	for i in range(1, 101):
		rs = (rs + A[i - 1][a] * A[i - 1][b]) % M
	print(rs)


import os
import sys

def twoSubsequences(x, r, s):
	if r < s or (r + s) % 2:
		return 0
	mod = 10 ** 9 + 7
	(sa, sb) = ((r + s) // 2, (r - s) // 2)
	maxL = sb // min(x)
	maxV = sa
	dp = [[0 for _ in range(maxV + 1)] for _ in range(maxL + 1)]
	dp[0][0] = 1
	for j in x:
		for l in range(maxL, 0, -1):
			for i in range(maxV, -1, -1):
				if i >= j:
					dp[l][i] += dp[l - 1][i - j]
					dp[l][i] %= mod
	res = 0
	for l in range(1, maxL + 1):
		res += dp[l][sa] * dp[l][sb]
		res %= mod
	return res
mrs = input().split()
m = int(mrs[0])
r = int(mrs[1])
s = int(mrs[2])
x = list(map(int, input().rstrip().split()))
result = twoSubsequences(x, r, s)
print(result)


import os
import sys
modulo = int(1000000000.0 + 7)
d_prev = []
d_at = []

def merge(d1, d2):
	ret = d1.copy()
	ret.update(d2)
	keys_d1 = set(d1.keys())
	keys_d2 = set(d2.keys())
	for k in keys_d1 & keys_d2:
		ret[k] += d1[k]
	return ret

def do_len(l, s_a, s_b):
	cnt_a = 0
	cnt_b = 0
	g_a = True
	g_b = True
	do_len.done = False
	top = m - l
	for i in range(0, top):
		d_at[i].clear()
		for (k, v) in d_prev[i + 1].items():
			new_key = k + X[i]
			if new_key == s_a:
				cnt_a += v
				cnt_a %= modulo
			if new_key == s_b:
				cnt_b += v
				cnt_b %= modulo
			if new_key < s_a:
				g_a = False
				d_at[i][new_key] = v % modulo
			if new_key < s_b:
				g_b = False
				d_at[i][new_key] = v % modulo
	if g_a and g_b:
		do_len.done = True
	if l != m and (not do_len.done):
		d_prev[top - 1] = d_at[top - 1]
		for i in range(top - 2, -1, -1):
			d_prev[i] = merge(d_prev[i + 1], d_at[i])
	return cnt_a * cnt_b % modulo
do_len.done = True

def answer():
	rps = r + s
	rms = r - s
	if rps <= 0 or rms <= 0 or rps % 2 == 1 or (rms % 2 == 1):
		return 0
	s_a = rps // 2
	s_b = rms // 2
	cnt = 0
	for l in range(0, m):
		cnt += do_len(l, s_a, s_b)
		cnt %= modulo
		if do_len.done:
			break
	return cnt
(m, r, s) = map(int, input().split())
X = list(map(int, input().split()))
for i in range(0, m + 1):
	d_prev.append({0: 1})
	d_at.append({})
print(answer())


from collections import Counter
MOD = 1000000007

def get_sums(seq, r, s):
	if (r + s) % 2 != 0:
		return 0
	if s > r:
		return 0
	a = (r + s) // 2
	b = r - a
	counts = [Counter()]
	for i in seq:
		counts.append(Counter())
		sub_length = len(counts) - 1
		while sub_length >= 2:
			current = counts[sub_length]
			prev = counts[sub_length - 1]
			for c in prev:
				if c + i <= r:
					current[c + i] += prev[c]
			sub_length -= 1
		counts[1][i] += 1
	total = 0
	for totals in counts:
		total += totals[a] * totals[b]
	return total
(count, r, s) = map(int, input().strip().split())
seq = map(int, input().strip().split())
print(get_sums(seq, r, s) % MOD)


from collections import Counter
MOD = 10 ** 9 + 7
(n, r, s) = map(int, input().split())
if (r ^ s) & 1:
	print(0)
	quit()
x = (r + s) // 2
y = (r - s) // 2
a = list(map(int, input().split()))
s = [Counter() for _ in range(n + 1)]
s[0][0] = 1
for (i, v) in enumerate(a):
	for j in range(i, -1, -1):
		s[j + 1] += Counter({k + v: e % MOD for (k, e) in s[j].items() if k + v <= x})
print(sum((c[x] * c[y] % MOD for c in s[1:])) % MOD)


def solve(a, m, x):
	tab = [[dict() for _ in range(a + 1)] for q in range(m)]
	for i in range(0, m):
		for j in range(a + 1):
			for k in range(0, i + 2):
				tab[i][j][k] = 0
	for u in range(m):
		tab[u][0][0] = 1
	for r in range(1, a + 1):
		if x[0] == r:
			tab[0][r][1] = 1
	for i in range(1, m):
		for j in range(1, a + 1):
			d_up = tab[i - 1][j]
			for key in d_up:
				tab[i][j][key] = d_up[key]
			if x[i] <= j:
				d = tab[i - 1][j - x[i]]
				for k in d.keys():
					tab[i][j][k + 1] += d[k]
	return tab[-1][-1]

def main():
	(m, r, s) = [int(x) for x in input().split()]
	x = [int(l) for l in input().split()]
	A = (r + s) / 2
	B = (r - s) / 2
	if A != int(A) or B != int(B) or B < 0 or (A < 0) or (not r and (not s)):
		print(0)
	else:
		A = int(A)
		B = int(B)
		d1 = solve(A, m, x)
		d2 = solve(B, m, x)
		res = 0
		for key in d1.keys():
			if key in d2.keys():
				res += d1[key] * d2[key]
				res = res % (10 ** 9 + 7)
		print(res)
main()


import math
mod = 10 ** 9 + 7

def solve():
	(m, r, s) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	print(number_of_subsequence_pairs(arr, r, s))

def number_of_subsequence_pairs(arr, r, s):
	target1 = r + s
	target2 = r - s
	m = len(arr)
	arr.insert(0, 0)
	memo = [[{} for j in range(m + 1)] for i in range(m + 1)]
	for j in range(1, m + 1):
		for i in range(j, m + 1):
			s_range = range(1, target1 + 1) if j == 1 else range(min(memo[i][j - 1]), target1 + 1) if len(memo[i][j - 1]) > 0 else range(0)
			for s in s_range:
				if j == 1:
					if s == arr[i] * 2:
						count = 1 + get_num_subsequences(i - 1, j, s, memo)
					else:
						count = get_num_subsequences(i - 1, j, s, memo)
				else:
					count = get_num_subsequences(i - 1, j - 1, s - arr[i] * 2, memo) + get_num_subsequences(i - 1, j, s, memo)
				if count != 0:
					memo[i][j][s] = count
	return combine_subsequence_pairs(target1, target2, memo, m)

def get_num_subsequences(i, j, s, memo):
	if i == 0 or j == 0 or s <= 0 or (s not in memo[i][j]):
		return 0
	else:
		return memo[i][j][s]

def combine_subsequence_pairs(target1, target2, memo, m):
	result = 0
	for j in range(1, m + 1):
		result += memo[m][j].get(target1, 0) * memo[m][j].get(target2, 0) % mod
		result %= mod
	return result
solve()


import os
import sys

def twoSubsequences(x, r, s):
	if r < s or (r + s) % 2:
		return 0
	mod = 10 ** 9 + 7
	(sa, sb) = ((r + s) // 2, (r - s) // 2)
	maxL = sb // min(x)
	maxV = sa
	dp = [[0 for _ in range(maxV + 1)] for _ in range(maxL + 1)]
	dp[0][0] = 1
	for j in x:
		for l in range(maxL, 0, -1):
			for i in range(maxV, -1, -1):
				if i >= j:
					dp[l][i] += dp[l - 1][i - j]
					dp[l][i] %= mod
	res = 0
	for l in range(1, maxL + 1):
		res += dp[l][sa] * dp[l][sb]
		res %= mod
	return res
mrs = input().split()
m = int(mrs[0])
r = int(mrs[1])
s = int(mrs[2])
x = list(map(int, input().rstrip().split()))
result = twoSubsequences(x, r, s)
print(result)


import math
mod = 10 ** 9 + 7

def solve():
	(m, r, s) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	print(number_of_subsequence_pairs(arr, r, s))

def number_of_subsequence_pairs(arr, r, s):
	target1 = r + s
	target2 = r - s
	m = len(arr)
	values = make_initial_value_set(arr, target1)
	arr.insert(0, 0)
	memo = [[{} for j in range(m + 1)] for i in range(m + 1)]
	for j in range(1, m + 1):
		for i in range(j, m + 1):
			s_range = calculate_sum_range(target1, values, i, j, memo)
			for s in s_range:
				count = count_subsequences(i, j, s, arr, memo)
				if count != 0:
					memo[i][j][s] = count
	return combine_subsequence_pairs(target1, target2, memo, m)

def make_initial_value_set(arr, target):
	return set([i * 2 for i in arr if i * 2 <= target])

def calculate_sum_range(target, values, i, j, memo):
	if j == 1:
		return values
	elif len(memo[i][j - 1]) > 0:
		return range(min(memo[i][j - 1]), target + 1)
	else:
		return range(0)

def count_subsequences(i, j, s, arr, memo):
	if j == 1:
		if s == arr[i] * 2:
			count = 1 + get_num_subsequences(i - 1, j, s, memo)
		else:
			count = get_num_subsequences(i - 1, j, s, memo)
	else:
		count = get_num_subsequences(i - 1, j - 1, s - arr[i] * 2, memo) + get_num_subsequences(i - 1, j, s, memo)
	return count

def get_num_subsequences(i, j, s, memo):
	return memo[i][j].get(s, 0)

def combine_subsequence_pairs(target1, target2, memo, m):
	result = 0
	for j in range(1, m + 1):
		result += memo[m][j].get(target1, 0) * memo[m][j].get(target2, 0) % mod
		result %= mod
	return result
solve()


def twoSubsequences(x, r, s):
	if r < s or (r + s) % 2:
		return 0
	mod = 10 ** 9 + 7
	(sa, sb) = ((r + s) // 2, (r - s) // 2)
	maxL = sb // min(x)
	maxV = sa
	dp = [[0 for _ in range(maxV + 1)] for _ in range(maxL + 1)]
	dp[0][0] = 1
	for j in x:
		for l in range(maxL, 0, -1):
			for i in range(maxV, -1, -1):
				if i >= j:
					dp[l][i] += dp[l - 1][i - j]
					dp[l][i] %= mod
	res = 0
	for l in range(1, maxL + 1):
		res += dp[l][sa] * dp[l][sb]
		res %= mod
	return res
mrs = input().split()
m = int(mrs[0])
r = int(mrs[1])
s = int(mrs[2])
x = list(map(int, input().rstrip().split()))
result = twoSubsequences(x, r, s)
print(result)


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def twoSubsequences(x, r, s):
	if r < s or (r + s) % 2:
		return 0
	mod = 10 ** 9 + 7
	(sa, sb) = ((r + s) // 2, (r - s) // 2)
	maxL = sb // min(x)
	maxV = sa
	dp = [[0 for _ in range(maxV + 1)] for _ in range(maxL + 1)]
	dp[0][0] = 1
	for j in x:
		for l in range(maxL, 0, -1):
			for i in range(maxV, -1, -1):
				if i >= j:
					dp[l][i] += dp[l - 1][i - j]
					dp[l][i] %= mod
	res = 0
	for l in range(1, maxL + 1):
		res += dp[l][sa] * dp[l][sb]
		res %= mod
	return res
mrs = input().split()
m = int(mrs[0])
r = int(mrs[1])
s = int(mrs[2])
x = list(map(int, input().rstrip().split()))
result = twoSubsequences(x, r, s)
print(result)


import math
import os
import random
import re
import sys

def twoSubsequences(x, r, s):
	if r < s or (r + s) % 2:
		return 0
	mod = 10 ** 9 + 7
	(sa, sb) = ((r + s) // 2, (r - s) // 2)
	maxL = sb // min(x)
	maxV = sa
	dp = [[0 for _ in range(maxV + 1)] for _ in range(maxL + 1)]
	dp[0][0] = 1
	for j in x:
		for l in range(maxL, 0, -1):
			for i in range(maxV, -1, -1):
				if i >= j:
					dp[l][i] += dp[l - 1][i - j]
					dp[l][i] %= mod
	res = 0
	for l in range(1, maxL + 1):
		res += dp[l][sa] * dp[l][sb]
		res %= mod
	return res
mrs = input().split()
m = int(mrs[0])
r = int(mrs[1])
s = int(mrs[2])
x = list(map(int, input().rstrip().split()))
result = twoSubsequences(x, r, s)
print(result)


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


(M, R, S) = map(int, input().split(' '))
X = list(map(int, input().split(' ')))
if R % 2 != S % 2:
	print(0)
else:
	Sa = (R + S) // 2
	Sb = (R - S) // 2
	if Sb < 0:
		print(0)
	else:
		DP = []
		for _ in range(M + 1):
			DP.append([0] * (Sa + 1))
		DP[0][0] = 1
		for i in range(len(X)):
			if X[i] <= Sa:
				for j in range(Sa - X[i], -1, -1):
					for k in range(i + 1):
						if DP[k][j] > 0:
							DP[k + 1][j + X[i]] += DP[k][j]
		ans = 0
		for i in range(1, len(X)):
			ans = (ans + DP[i][Sa] * DP[i][Sb]) % (10 ** 9 + 7)
		print(ans)


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


import math
import os
import random
import re
import sys

def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())


import math
import os
import random
import re
import sys

def solve():
	mod = 10 ** 9 + 7
	(m, r, s) = map(int, input().rstrip().split(' '))
	if m == 0 or r <= s:
		return 0
	arr = list(map(int, input().rstrip().split(' ')))
	if (r - s) % 2 != 0:
		return 0
	sumb = (r - s) // 2
	suma = r - sumb

	def get_ways(num):
		dp = [[0] * (num + 1) for _ in range(m + 1)]
		dp[0][0] = 1
		for c in arr:
			for i in range(len(dp[0]) - 1, c - 1, -1):
				for j in range(len(dp) - 2, -1, -1):
					if dp[j][i - c] > 0:
						dp[j + 1][i] += dp[j][i - c]
		for j in range(len(dp)):
			if dp[j][num] > 0:
				yield (j, dp[j][num])
	a = list(get_ways(suma))
	b = list(get_ways(sumb))
	res = 0
	for i in a:
		for j in b:
			if i[0] == j[0]:
				res += i[1] * j[1]
	return res % mod
print(solve())