配点: 100 点
問題
Pitaro 和你正在玩一个有趣、有趣、有趣的游戏。
皮塔罗是 10 以十进制表示 它是一个包含 N 位的正整数。这个数字的开头是 这不是 0 。
Pitaro 从最高位开始执行此操作。 1 一位一位读出数字。每次 Pitaro 说出一个数字时,您都会通过按读取顺序排列 Pitaro 迄今为止读取的数字(从最高位开始)来创建一个整数。 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 请注意,这不被视为数字。