给你一个由非负整数组成的序列。在一步操作中,你可以选择任意两个相邻的正数,并将它们都减 1。如果序列中没有可行的操作(即不存在相邻的两个正数),则称该序列为“好的”(good)。
计算从给定的初始序列出发,通过若干次操作可以得到的不同“好的”序列的数量。答案可能很大,请将其对 $10^9 + 7$ 取模后输出。
输入格式
输入的第一行包含一个整数 $N$ ($1 \le N \le 100\,000$),表示序列的长度。
第二行包含 $N$ 个非负整数,表示初始序列。序列中的每个元素都不超过 300。
输出格式
输出可以得到的不同“好的”序列的数量,对 $10^9 + 7$ 取模。
样例
输入样例 1
2 4 2
输出样例 1
1
输入样例 2
3 1 2 3
输出样例 2
2