001 - 白黒すごろく

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 5 /


TLE
1sec
MLE
64MB
得点
100

問題

そろそろ正月が近くなった12月、ジェイ君の家ですごろく大会を開くことになった。
それに備えるために、すごろくに使うボードをあらかじめチェックすることにした。
ボードには1〜N番の番号がついた白色か黒色のマスがあり、1番からスタートし番号順に進みN番のマスにぴったりつくとゴールとなる。
仮にNのマスを超えてしまった場合や、黒いマスに止まった場合は失格となりゴールできない。
また、1番のマスとN番のマスは白色のマスである。
また、手元には1〜6の目があるさいころがあり、これを振って出た目の数だけ駒を進める。
今回あなたはゴールする方法が何通りあるのかを調べることにした。 ただし、場合によってはとても大きな数になってしまうため、10007で割った余りを求めることにした。

入力

N M
b1
b2
.
.
.
bM

1行目にマスの数Nと黒色のマスの数Mが与えられる。
2行目からM行にかけて黒色のマスの番号biが与えられる。この中に1とNは必ず登場しない。

出力

黒色のマスに移動せずちょうどNのマスに止まる方法の数を10007で割った余りを出力せよ。
最後に改行を忘れないこと。

制約

全ての入出力ケースについて以下を満たす。

  • 2≦N≦105
  • 0≦M≦N-2
  • i≠jの時bi≠bj

入出力例

入力例1

8 3
3
5
6

出力例1

7

解説

以下の7つの方法がある。
1→2→8
1→2→4→8
1→2→7→8
1→2→4→7→8
1→4→8
1→4→7→8
1→7→8

入力例2

8 6
2
3
4
5
6
7

出力例2

0

入力例3

100000 0

出力例3

9565

解説

実際はとても大きな値なのだが、10007で割った余りの9565を出力する。

入力例4

30 7
8
20
27
23
22
3
2

出力例4

1016