#P1470. 2023.08.19-MT-第四题-塔子哥的数组

2023.08.19-MT-第四题-塔子哥的数组

题目内容

塔子哥有一个长度为 nn 的数组 aa ,现在他想要重新构造一个长度也为 nn 的数组 bb ,满足如下三个条件,就是塔子哥要构造的数组 bb

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

  • aibi(1in)a_i\neq b_i (1\leq i\leq n)

  • bi>0b_i > 0

现在塔子哥想问你,可以构造出多少种不同的数组 bb ,答案对 109+710^9+7 取模。

输入描述

第一行,一个正整数 n(1n100)n(1\leq n\leq 100) ,表示数组 aabb 的大小

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

输出描述

输出一个整数,表示构造出的不同的数组 bb 的方案数,答案对 109+710^9+7 取模。

样例

输入

3
1 2 3

输出

3