{"trustable":true,"prependHtml":"\u003cstyle\u003e.table {width: 100%;} .table-bordered {border: 1px solid #222; border-collapse: collapse; border-spacing: 0;} .table-bordered th { border: 1px solid #222; }.table-bordered td { border: 1px solid #222; padding: 0 5px; }\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e$5$ 月 $9$ 日,跳蚤王国建好了第 $509$ 号迷宫。迷宫为一个 $(n+1)\\times (n+1)$ 的正方形点阵,点的坐标为 $(i,j)\\ (0 \\le i,j \\le n)$。\u003c/p\u003e\n\u003cp\u003e因为这个迷宫是 $5$ 月 $9$ 日建造的,$n$ 是 $509$ 的倍数。\u003c/p\u003e\n\u003cp\u003e迷宫除了第 $0$ 行的每一行都有一个有陷阱的点。求出从 $(0,0)$ 到 $(n,n)$ 的不经过陷阱的,每一步均为往右(也即坐标增加 $(1,0)$)或者往上(也即坐标增加 $(0,1)$)的路径数。同样的,由于这是第 $509$ 号迷宫,答案对 $509$ 取模。\u003c/p\u003e\n\u003ch3\u003e输入格式\u003c/h3\u003e\n\u003cp\u003e第一行一个整数 $n$ 表示迷宫的大小。第二行为 $n$ 个整数 $a_i\\ (0 \\le a_i \\le n)$,表示第 $i$ 行的陷阱位置。\u003c/p\u003e\n\u003ch3\u003e输出格式\u003c/h3\u003e\n\u003cp\u003e一行一个整数,表示答案对 $509$ 取模后的余数。\u003c/p\u003e\n\u003ch3\u003e样例零\u003c/h3\u003e\n\u003ch4\u003einput\u003c/h4\u003e\n\u003cpre\u003e2\n0 1\u003c/pre\u003e\u003ch4\u003eoutput\u003c/h4\u003e\n\u003cpre\u003e2\u003c/pre\u003e\u003ch4\u003eexplanation\u003c/h4\u003e\n\u003cp\u003e两个陷阱的位置为 $(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$,仅用于说明题意,不会放入测试中。\u003c/p\u003e\n\u003ch3\u003e样例一\u003c/h3\u003e\n\u003cp\u003e见下发文件。本样例满足子任务 1 的限制。\u003c/p\u003e\n\u003ch3\u003e样例二\u003c/h3\u003e\n\u003cp\u003e见下发文件。本样例满足子任务 4 的限制。\u003c/p\u003e\n\u003ch3\u003e样例三\u003c/h3\u003e\n\u003cp\u003e见下发文件。本样例满足子任务 5 的限制。\u003c/p\u003e\n\u003ch3\u003e样例四\u003c/h3\u003e\n\u003cp\u003e见下发文件。本样例满足子任务 6 的限制。\u003c/p\u003e\n\u003ch3\u003e限制与约定\u003c/h3\u003e\n\u003cp\u003e\u003cstrong\u003e本题采用捆绑测试。\u003c/strong\u003e\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eSubtask 1(7 points):$n\u003d509$。\u003c/li\u003e\n\u003cli\u003eSubtask 2(8 points):$a_n\u003dn$。\u003c/li\u003e\n\u003cli\u003eSubtask 3(10 points):$a_i\u003d1\\ (2 \\le i \\le n)$。\u003c/li\u003e\n\u003cli\u003eSubtask 4(21 points):$a_i\u003di-509\\ (509 \\le i \\le n)$。\u003c/li\u003e\n\u003cli\u003eSubtask 5(25 points):$n\u003d152700$。\u003c/li\u003e\n\u003cli\u003eSubtask 6(29 points):无特殊限制。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e对于 $100\\%$ 的数据,$1 \\le n \\le 254500$,$0 \\le a_i \\le n$,除样例零外,$n$ 是 $509$ 的倍数。\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e时间限制:$\\texttt{3s}$\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e空间限制:$\\texttt{512MB}$\u003c/strong\u003e\u003c/p\u003e\n"}}]}