问题文

可以在黑板上写入从 1 到 T 的整数。对于每个 i，可以用 0 到 ai 个数写在黑板上。

经过下面的操作，重复进行，直到只剩下一个整数在黑板上：

• 如果黑板上有两个或更多相同的整数 X，可以将这两个整数擦掉，然后在黑板上写入 X+1。

请问，有多少种不同的方法可以使得最终只剩下一个整数在黑板上？

答案可能非常大，请将答案对 $10^9+7$ 取模。

这里，两种写法被认为是不同的，当且仅当它们在操作开始之前黑板上的整数个数不同。

约束条件

• $1 \leq T \leq 300$
• $0 \leq a_i \leq 300$
• 所有输入都是整数

输入

输入从标准输入读取，具有以下格式：

$T$ $a_1$ $a_2$ ... $a_{T-1}$ $a_T$

输出

输出一个整数，表示通过操作得到只有一个整数在黑板上的不同方法的数量，对 $10^9+7$ 取模。

输入例子 1

2
1 1

输出例子 1

2

可以写入 1 或者写入 2，满足条件。

输入例子 2

3
2 1 1

输出例子 2

6

输入例子 3

8
300 300 300 300 300 300 300 300

输出例子 3

220439161