$5$ 月 $9$ 日，跳蚤王国建好了第 $509$ 号迷宫。迷宫为一个 $(n+1)\times (n+1)$ 的正方形点阵，点的坐标为 $(i,j)\ (0 \le i,j \le n)$。

因为这个迷宫是 $5$ 月 $9$ 日建造的，$n$ 是 $509$ 的倍数。

迷宫除了第 $0$ 行的每一行都有一个有陷阱的点。求出从 $(0,0)$ 到 $(n,n)$ 的不经过陷阱的，每一步均为往右（也即坐标增加 $(1,0)$）或者往上（也即坐标增加 $(0,1)$）的路径数。同样的，由于这是第 $509$ 号迷宫，答案对 $509$ 取模。

输入格式

第一行一个整数 $n$ 表示迷宫的大小。第二行为 $n$ 个整数 $a_i\ (0 \le a_i \le n)$，表示第 $i$ 行的陷阱位置。

输出格式

一行一个整数，表示答案对 $509$ 取模后的余数。

样例零

input

2
0 1

output

2

explanation

两个陷阱的位置为 $(1,0),(2,1)$，共有两条可能的路径 $(0,0)\to (0,1)\to (0,2)\to (1,2)\to (2,2)$ 和 $(0,0)\to (0,1)\to (1,1)\to (1,2)\to (2,2)$。 本样例不满足 $509 \mid n$，仅用于说明题意，不会放入测试中。

样例一

见下发文件。本样例满足子任务 1 的限制。

样例二

见下发文件。本样例满足子任务 4 的限制。

样例三

见下发文件。本样例满足子任务 5 的限制。

样例四

见下发文件。本样例满足子任务 6 的限制。

限制与约定

本题采用捆绑测试。

• Subtask 1（7 points）：$n=509$。
• Subtask 2（8 points）：$a_n=n$。
• Subtask 3（10 points）：$a_i=1\ (2 \le i \le n)$。
• Subtask 4（21 points）：$a_i=i-509\ (509 \le i \le n)$。
• Subtask 5（25 points）：$n=152700$。
• Subtask 6（29 points）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 254500$，$0 \le a_i \le n$，除样例零外，$n$ 是 $509$ 的倍数。

时间限制：$\texttt{3s}$

空间限制：$\texttt{512MB}$