小美拿到了一个数组，她准备构造一个数组 $b$ 满足： 1.$b$ 的每一位都和 $a$ 对应位置不同，即 $b_i≠a_i$ 2.$b$ 的所有元素之和都和α相同。 3.$b$ 的数组均为正整数。
请你告诉小美有多少种构造方式。由于答案过大，请对 $10^9+7$ 取模。
输入描述
第一行输入一个正整数 $n$，代表数组的大小。 第二行输入个 $n$ 正整数 $a_i$ , 代表小美拿到的数组。
- $1≤n≤100$
- $1≤a_i≤300$
- $1≤\sum a_i ≤500$
输出描述
一个整数，代表构造方式对 $10^9+7$ 取模的值。
样例
输入
3
1 1 3
输出
1
样例解释
只有 [2,2,1] 满足条件。
输入
3
1 1 1
输出
0
说明
样例解释
没有满足条件的数组。
思路
主要是利用 dp 算法，dp[i][j]表示前i个数和为j的方案数，那么dp[i][j] = sum(dp[i-1][j-k])，其中k为 1 到j的数，但是要注意k不能等于a[i]，因为题目要求b[i]不能等于a[i]。
答案
n = int(input())
a = list(map(int, input().split()))
# n = 3
# a = [10, 3, 3]
MOD = 10**9 + 7
s = sum(a)
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(1, s + 1):
for k in range(1, j + 1):
if k != a[i - 1]:
dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD
print(dp[n][s])
