题目描述

一轮想要构造一棵有 $n$ 个节点的树，但由于选择困难，他不太确定如何构造才最合适。不过，一轮能够确定每个节点的深度。现在，请你告诉一轮满足这些深度限制的树一共有多少种不同的构造方案。

树是有根树，节点从 $1$ 到 $n$ 编号。

如果两棵树中存在至少一个节点的父节点不同，则认为它们是不同的树。

深度为 $0$ 的节点为根节点，有且仅有一个。

答案可能很大，请将方案数对 $1000000007$ 取模后输出。

题目保证至少有一种满足条件的树。

输入格式

第一行一个整数 $n$ ，表示节点个数。

接下来 $n$ 行，每行一个整数，第 $i$ 行的整数表示节点 $i$ 的深度（根的深度为 $0$ ）。

一个整数，表示满足条件的树的数量对 1000000007 取模后的结果。

$1 \le n \le 10^5。$

$0 \le d_i \le n-1。$