太郎有N只兔子，现在为了方便识别它们，太郎要给他们编号。兔子们向太郎表达了它们对号码的喜好。 每个兔子i想要一个整数，介于1和Mi之间(可以为1或Mi)。当然，每个兔子的编号是不同的。现在太郎想知道一共有多少种编号的方法。 你只用输出答案对1000000000+7取余的结果即可。如果这是不可能的，就输出0。
输入
第一行是一个整数N。 第二行N个整数Mi。
输出
一个整数，表示方案总数。
样例
| 标准输入 复制文本 |
2 5 8 |
| 标准输出 复制文本 |
35 |
提示
对于全部数据，1≤N≤50,1≤Mi≤1000。