C - 階段の上り方 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は N 段の階段の前に立っています。高橋君は現在 0 段目（地面）にいて、N 段目（頂上）まで上ることを目指します。

高橋君は1回の移動で、現在いる段から 1 段上、2 段上、または 3 段上の段へ移動することができます。すなわち、現在 i 段目にいるとき、i+1 段目、i+2 段目、i+3 段目のいずれかへ直接移動できます。ただし、移動先の段にのみ着地し、途中の段には着地しません。

階段のいくつかの段は老朽化しており壊れています。壊れている段は M 個あり、それぞれ B_1, B_2, \ldots, B_M 段目です（B_i はすべて異なります）。壊れている段に着地することはできません。ただし、壊れている段を飛び越えること（着地せずに通過すること）は可能です。例えば、i+1 段目が壊れていても、i 段目から i+2 段目や i+3 段目へ移動することができます。なお、0 段目（地面）と N 段目（頂上）は壊れていないことが保証されています。

高橋君が 0 段目から N 段目まで上る方法の数を求めてください。ただし、上り方が1通りも存在しない場合は 0 とします。答えは非常に大きくなる可能性があるため、10^9 + 7 で割った余りを出力してください。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq N - 1
  • 1 \leq B_i \leq N - 1 (1 \leq i \leq M)
  • B_i はすべて異なる
  • B_1, B_2, \ldots, B_M は昇順とは限らない
  • 入力はすべて整数

入力

N M
B_1 B_2 \ldots B_M
  • 1 行目には、階段の段数を表す整数 N と、壊れている段の数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、壊れている段の番号を表す M 個の整数 B_1, B_2, \ldots, B_M が、スペース区切りで与えられる。順序は不定である。M = 0 の場合、2 行目は与えられない。

出力

高橋君が 0 段目から N 段目まで上る方法の数を 10^9 + 7 で割った余りを 1 行で出力せよ。

入力例 1

5 1
3

出力例 1

5

入力例 2

4 3
1 2 3

出力例 2

0

入力例 3

20 3
5 10 15

出力例 3

6728

入力例 4

1000 5
100 200 300 400 500

出力例 4

935523008

入力例 5

1 0

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi is standing in front of a staircase with N steps. Takahashi is currently on step 0 (the ground) and aims to reach step N (the top).

In one move, Takahashi can move from his current step to the step that is 1 step above, 2 steps above, or 3 steps above. That is, when he is currently on step i, he can directly move to step i+1, step i+2, or step i+3. However, he only lands on the destination step and does not land on any intermediate steps.

Some steps of the staircase are deteriorated and broken. There are M broken steps, which are steps B_1, B_2, \ldots, B_M (all B_i are distinct). It is not possible to land on a broken step. However, it is possible to jump over a broken step (passing it without landing). For example, even if step i+1 is broken, Takahashi can move from step i to step i+2 or step i+3. It is guaranteed that step 0 (the ground) and step N (the top) are not broken.

Find the number of ways Takahashi can climb from step 0 to step N. If there is no valid way to climb, output 0. Since the answer can be very large, output the remainder when divided by 10^9 + 7.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq M \leq N - 1
  • 1 \leq B_i \leq N - 1 (1 \leq i \leq M)
  • All B_i are distinct
  • B_1, B_2, \ldots, B_M are not necessarily in ascending order
  • All inputs are integers

Input

N M
B_1 B_2 \ldots B_M
  • The first line contains an integer N representing the number of steps and an integer M representing the number of broken steps, separated by a space.
  • The second line contains M integers B_1, B_2, \ldots, B_M representing the numbers of the broken steps, separated by spaces. The order is arbitrary. If M = 0, the second line is not given.

Output

Output in one line the number of ways Takahashi can climb from step 0 to step N, modulo 10^9 + 7.

Sample Input 1

5 1
3

Sample Output 1

5

Sample Input 2

4 3
1 2 3

Sample Output 2

0

Sample Input 3

20 3
5 10 15

Sample Output 3

6728

Sample Input 4

1000 5
100 200 300 400 500

Sample Output 4

935523008

Sample Input 5

1 0

Sample Output 5

1