D - FizzBuzz (FizzBuzz)

Time Limit: 2 sec / Memory Limit: 256 MB

配点: 100

問題

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

ピ太郎は 10 進法で N 桁の正の整数を持っている.この数の先頭は 0 ではない.

ピ太郎はこれを上の桁から 1 桁ずつ読み上げていく.あなたはピ太郎が数字を言うたびに,ピ太郎がそれまで読み上げた数字を読み上げた順に上の桁から並べてできる整数を K とし,K3 の倍数であり 5 の倍数でないなら Fizz5 の倍数であり 3 の倍数でないなら Buzz15 の倍数なら FizzBuzz と発言する.K3 の倍数でも 5 の倍数でもないならあなたは何も言わない.例えばピ太郎が 12\,345\,670 という数を読み上げていくと,あなたは FizzFizzFizzBuzzFizzBuzz5 回発言することになる.

あなたはゲームのプレイ記録を確認している.記録にはあなたがちょうど 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_iFizzBuzzFizzBuzz のいずれかである (1 \leq i \leq M)

小課題

  1. (10 点) N \leq 6
  2. (2 点) N = MS_i (1 \leq i \leq N)FizzBuzz
  3. (14 点) N = MS_i (1 \leq i \leq N)Fizz
  4. (14 点) N = MS_i (1 \leq i \leq N)Buzz
  5. (20 点) N = M
  6. (40 点) 追加の制約はない.

入力

入力は以下の形式で標準入力から与えられる.

N M
S_1
\vdots
S_M

出力

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


入力例 1

3 2
Buzz
FizzBuzz

出力例 1

7

105255405525585705855 が与えられた記録を満たしている.


入力例 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

例えば 0107 といった数は 2 桁とはみなされないので注意せよ.