题目内容

塔子哥有一个长度为 $n$ 的数组 $a$ ，现在他想要重新构造一个长度也为 $n$ 的数组 $b$ ，满足如下三个条件，就是塔子哥要构造的数组 $b$ 。

• $\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^n b_i$

• $a_i\neq b_i (1\leq i\leq n)$

• $b_i > 0$

现在塔子哥想问你，可以构造出多少种不同的数组 $b$ ，答案对 $10^9+7$ 取模。

输入描述

第一行，一个正整数 $n(1\leq n\leq 100)$ ，表示数组 $a$ 和 $b$ 的大小

第二行，$n$ 个正整数 $a_i(1\leq a_i\leq 300, \sum\limits_{i=1}^n a_i\leq 500)$

输出描述

输出一个整数，表示构造出的不同的数组 $b$ 的方案数，答案对 $10^9+7$ 取模。

样例

输入

3
1 2 3

输出

3