No testdata at current.

题目描述

一个$N$的排列$b_1,b_2,b_3,\cdots,b_{N}$是符合下列条件的一个序列：

1. $b_1~b_N$由$1~N$这$N$个数字组成
2. 每个数字只出现$1$次。

现在我们想知道，对于任意一个数$i$，要求满足$b_1,b_2,b_3,\cdots,b_{i}$中，小于等于$i$的数的个数恰好为$a_i$的序列一共有多少个。

输入格式

第一行一个数$N$，表示序列长度。

接下$N$个数$a_1,a_2,a_3,\cdots,a_{N}$ 。

输出格式

一个数，满足条件的排列数。

由于答案很大，只要求输出答案 $mod$ $340610$ 的结果。

样例

样例输入

3
0 1 3

样例输出

3

数据范围与提示

对于$30\%$数据, $1<n<10$；

对于$70\%$数据，$1<n<200$；

对于$100\%$数据，$1<n<10000$。