← 返回题目列表

AtCoder · otemae2019_d

D. 菲兹巴兹 (菲兹巴兹)

中文机器翻译题面 查看原题

配点: 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).

小課題

  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 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

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 请注意,这不被视为数字。