20240107 : 号码牌

P4 : 号码牌

描述

为了让幼儿园的小朋友记住自己上课的座位，老师计划给每个小朋友分配一个号码牌。幼儿园共有N名小朋友，每个小朋友的号码都应该是不同的。

然而，每个小朋友都有自己喜爱的数字。具体来说，第i个小朋友可以接受1~ai之间的号码。老师想知道是否能够满足所有小朋友的要求，如果可以，求出一共有多少种编号的方法。

答案可能很大，输出答案% 1000000007即可。如果不能满足所有小朋友的要求，就输出0。

输入

输入文件第一行给出一个整数N，第二行有N个整数，第i个整数表示ai。

输出

输出文件只有一行一个整数。

样例

2
5 8

2
1 1

提示

对于100%的数据，1≤N≤50，1≤ai≤1000。