問題

ピ太郎とあなたは楽しい楽しい楽しいゲームをしている．

ピ太郎は 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 で割った余りを求めるプログラムを作成せよ．

制約

• 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 点) 追加の制約はない．

入力例 1

3 2
Buzz
FizzBuzz

出力例 1

7

105，255，405，525，585，705，855 が与えられた記録を満たしている．

入力例 2

2 2
Buzz
FizzBuzz

出力例 2

0

入力例 3

1 0

出力例 3

5

入力例 4

10 5
Fizz
FizzBuzz
Fizz
Buzz
FizzBuzz

出力例 4

3232774

入力例 5

2 1
FizzBuzz

出力例 5

3

例えば 01 や 07 といった数は 2 桁とはみなされないので注意せよ．