Time Limit: 2 sec / Memory Limit: 256 MB
配点: 100 点
問題
ピ太郎とあなたは楽しい楽しい楽しいゲームをしている.
ピ太郎は 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).
小課題
- (10 点) N \leq 6.
- (2 点) N = M,S_i (1 \leq i \leq N) は
FizzBuzz
. - (14 点) N = M,S_i (1 \leq i \leq N) は
Fizz
. - (14 点) N = M,S_i (1 \leq i \leq N) は
Buzz
. - (20 点) N = M.
- (40 点) 追加の制約はない.
入力
入力は以下の形式で標準入力から与えられる.
N M S_1 \vdots S_M
出力
標準出力に,条件を満たす正の整数の個数を 1\,000\,000\,007 で割った余りを 1 行で出力せよ.
入力例 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 桁とはみなされないので注意せよ.