一个图有 $n$ 个顶点，每条边长度为 $1$，没有重边，满足从顶点 $1$ 到顶点 $i$ 的最短距离为 $A_i$。

计算符合条件的图总数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，分别为 $A_1$ 到 $A_n$。

输出格式

一行，一个整数，为符合条件的图总数 ${}\bmod1000000007$。

样例解释

第二，三组样例输出都是 $0$。