AT_otemae2019_d FizzBuzz (FizzBuzz)

[problemUrl]: https://atcoder.jp/contests/otemae2019/tasks/otemae2019_d ピ太郎とあなたは楽しい楽しい楽しいゲームをしている． ピ太郎は $ 10 $ 進法で $ N $ 桁の正の整数を持っている．この数の先頭は $ 0 $ ではない． ピ太郎はこれを上の桁から $ 1 $ 桁ずつ読み上げていく．あなたはピ太郎が数字を言うたびに，ピ太郎がそれまで読み上げた数字を読み上げた順に上の桁から並べてできる整数を $ K $ とし，$ K $ が $ 3 $ の倍数であり $ 5 $ の倍数でないなら `Fizz`，$ 5 $ の倍数であり $ 3 $ の倍数でないなら `Buzz`，$ 15 $ の倍数なら `FizzBuzz` と発言する．$ K $ が $ 3 $ の倍数でも $ 5 $ の倍数でもないならあなたは何も言わない．例えばピ太郎が $ 12\,345\,670 $ という数を読み上げていくと，あなたは `Fizz`，`Fizz`，`FizzBuzz`，`Fizz`，`Buzz` と $ 5 $ 回発言することになる． あなたはゲームのプレイ記録を確認している．記録にはあなたがちょうど $ M $ 回だけ発言したことと，$ i $ $ (1\ \leq\ i\ \leq\ M) $ 回目の発言が $ S_i $ であったことが書かれている． この記録を満たす $ N $ 桁の正の整数としてありえるものの個数を $ 1\,000\,000\,007 $ で割った余りを求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ S_1 $ $ \vdots $ $ S_M $

標準出力に，条件を満たす正の整数の個数を $ 1\,000\,000\,007 $ で割った余りを $ 1 $ 行で出力せよ．

### 制約 - $ 1\ \leq\ N\ \leq\ 1\,000 $． - $ 0\ \leq\ M\ \leq\ N $． - $ S_i $ は `Fizz`，`Buzz`，`FizzBuzz` のいずれかである $ (1\ \leq\ i\ \leq\ M) $． ### 小課題 1. ($ 10 $ 点) $ N\ \leq\ 6 $． 2. ($ 2 $ 点) $ N\ =\ M $，$ S_i $ $ (1\ \leq\ i\ \leq\ N) $ は `FizzBuzz`． 3. ($ 14 $ 点) $ N\ =\ M $，$ S_i $ $ (1\ \leq\ i\ \leq\ N) $ は `Fizz`． 4. ($ 14 $ 点) $ N\ =\ M $，$ S_i $ $ (1\ \leq\ i\ \leq\ N) $ は `Buzz`． 5. ($ 20 $ 点) $ N\ =\ M $． 6. ($ 40 $ 点) 追加の制約はない． ### Sample Explanation 1 $ 105 $，$ 255 $，$ 405 $，$ 525 $，$ 585 $，$ 705 $，$ 855 $ が与えられた記録を満たしている． ### Sample Explanation 5 例えば `01` や `07` といった数は $ 2 $ 桁とはみなされないので注意せよ．