题目描述

小爱想要画一棵 $n$ 个节点的有根树，节点编号分别为$1..n$，他告诉了你他希望每个节点在这棵树上的深度 $d_i$，其中根节点深度为 $1$。

请你根据给定信息，帮忙计算出有多少棵树满足小爱的要求？由于答案可能很大，请你输出对 $10^9+7$ 取模后的结果。

输入格式

输入共两行， 第一行，一个正整数 $n$ ，表示节点个数 第二行，$n$ 个正整数 $d_1,d_2,...,d_n$，分别表示每个节点的深度

输出格式

输出共一行，表示答案。

4
2 1 2 3

2

样例解释 1

2号点为根，1号点、3号点分别为2号点的儿子。4号点可以是1号点的儿子，也可以是3号点的儿子，共两种

数据范围

• 对于 $30\%$的数据，$1 \leq n \leq 10$
• 对于 $60\%$的数据，$1 \leq n \leq 10^3$
• 对于 $100\%$的数据，$1 \leq n \leq 10^5$