{"raw_statement":[{"iden":"background","content":"译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Impreza krasnali](https://sio2.mimuw.edu.pl/c/oi29-1/p/imp/)。"},{"iden":"statement","content":"有 $n$ 个人依次站成一排，每个人手上都有一个数字，这 $n$ 个数字形成一个排列。\n\n每个人会二选一地报告他左边或右边的人手上的数字。注意第一个人与第 $n$ 个人并不相邻，所以第一个人总是会报告第二个人的数字，第 $n$ 个人总是会报告第 $n-1$ 个人的数字。\n\n现在你得到了 $n$ 个人报告的数字，求出原先的排列有多少种可能。"},{"iden":"input","content":"第一行一个正整数 $n$。\n\n第二行 $n$ 个整数，表示每个人报告的数字。"},{"iden":"output","content":"一行一个整数，你的答案模 $10^9+7$。"},{"iden":"note","content":"对于所有数据，$2\\leq n\\leq 100000$。\n\n| 子任务编号 | 附加限制 | 分数 |\n| :----------: | :----------: | :----------: |\n| 1 | $n\\leq 10$ | 12 |\n| 2 | $n\\leq 20$ | 30 |\n| 3 | $n\\leq 1000$ | 30 |\n| 4 |  | 28 |"}],"translated_statement":null,"sample_group":[["5\n3 4 3 4 1\n","2\n"],["见附件","0"],["见附件","1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}