{"problem":{"name":"Typical Stairs","description":{"content":"There is a staircase with $N$ steps. Takahashi is now standing at the foot of the stairs, that is, on the $0$\\-th step. He can climb up one or two steps at a time. However, the treads of the $a_1$\\-th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc129_c"},"statements":[{"statement_type":"Markdown","content":"There is a staircase with $N$ steps. Takahashi is now standing at the foot of the stairs, that is, on the $0$\\-th step. He can climb up one or two steps at a time.\nHowever, the treads of the $a_1$\\-th, $a_2$\\-th, $a_3$\\-th, $\\ldots$, $a_M$\\-th steps are broken, so it is dangerous to set foot on those steps.\nHow many are there to climb up to the top step, that is, the $N$\\-th step, without setting foot on the broken steps? Find the count modulo $1\\ 000\\ 000\\ 007$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $0 \\leq M \\leq N-1$\n*   $1 \\leq a_1 < a_2 < $ $...$ $< a_M \\leq N-1$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$\n$a_2$\n $ .$\n $ .$\n $ .$\n$a_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc129_c","tags":[],"sample_group":[["6 1\n3","4\n\nThere are four ways to climb up the stairs, as follows:\n\n*   $0 \\to 1 \\to 2 \\to 4 \\to 5 \\to 6$\n*   $0 \\to 1 \\to 2 \\to 4 \\to 6$\n*   $0 \\to 2 \\to 4 \\to 5 \\to 6$\n*   $0 \\to 2 \\to 4 \\to 6$"],["10 2\n4\n5","0\n\nThere may be no way to climb up the stairs without setting foot on the broken steps."],["100 5\n1\n23\n45\n67\n89","608200469\n\nBe sure to print the count modulo $1\\ 000\\ 000\\ 007$."]],"created_at":"2026-03-03 11:01:14"}}