UOJ Logo Universal Online Judge

UOJ

附件下载 统计

$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}$