問題
そろそろ正月が近くなった１２月、ジェイ君の家ですごろく大会を開くことになった。
それに備えるために、すごろくに使うボードをあらかじめチェックすることにした。
ボードには1〜N番の番号がついた白色か黒色のマスがあり、１番からスタートし番号順に進みN番のマスにぴったりつくとゴールとなる。
仮にNのマスを超えてしまった場合や、黒いマスに止まった場合は失格となりゴールできない。
また、1番のマスとN番のマスは白色のマスである。
また、手元には１〜６の目があるさいころがあり、これを振って出た目の数だけ駒を進める。
今回あなたはゴールする方法が何通りあるのかを調べることにした。
ただし、場合によってはとても大きな数になってしまうため、10007で割った余りを求めることにした。
入力
N M b1 b2 . . . bM
１行目にマスの数Nと黒色のマスの数Mが与えられる。
２行目から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
解説
以下の７つの方法がある。
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