Problem Description

Pitaro and you are playing a fun and exciting game.

Pitaro has a positive integer with $N$ digits in base 10. The leading digit of this number is not zero.

Pitaro reads this number digit by digit from the highest place. Each time Pitaro says a digit, you form an integer $K$ by arranging the digits Pitaro has read so far in the order they were read from the highest place. If $K$ is a multiple of 3 but not a multiple of 5, you say Fizz. If $K$ is a multiple of 5 but not a multiple of 3, you say Buzz. If $K$ is a multiple of 15, you say FizzBuzz. If $K$ is neither a multiple of 3 nor a multiple of 5, you say nothing. For example, if Pitaro reads the number $12345670$, you will say Fizz, Fizz, FizzBuzz, Fizz, Buzz five times.

You are checking the game's play record. The record states that you made exactly $M$ utterances, and the $i$-th utterance ($1 \leq i \leq M$) was $S_i$.

Write a program to find the number of possible $N$-digit positive integers that satisfy this record, modulo $1,000,000,007$.

Input Format

The input is given from the standard input in the following format:

$N$ $M$ $S_1$ $\vdots$ $S_M$

Output Format

Output the number of positive integers that satisfy the conditions, modulo $1,000,000,007$, in one line to the standard output.

Sample Input and Output

Sample Input #1

3 2
Buzz
FizzBuzz

Sample Output #1

7

Sample Input #2

2 2
Buzz
FizzBuzz

Sample Output #2

0

Sample Input #3

1 0

Sample Output #3

5

Sample Input #4

10 5
Fizz
FizzBuzz
Fizz
Buzz
FizzBuzz

Sample Output #4

3232774

Sample Input #5

2 1
FizzBuzz

Sample Output #5

3

Notes/Hints

Constraints

• $1 \leq N \leq 1,000$.
• $0 \leq M \leq N$.
• $S_i$ is either Fizz, Buzz, or FizzBuzz ($1 \leq i \leq M$).

Subtasks

1. ($10$ points) $N \leq 6$.
2. ($2$ points) $N = M$, $S_i$ ($1 \leq i \leq N$) is FizzBuzz.
3. ($14$ points) $N = M$, $S_i$ ($1 \leq i \leq N$) is Fizz.
4. ($14$ points) $N = M$, $S_i$ ($1 \leq i \leq N$) is Buzz.
5. ($20$ points) $N = M$.
6. ($40$ points) No additional constraints.

Sample Explanation 1

$105$, $255$, $405$, $525$, $585$, $705$, $855$ satisfy the given record.

Sample Explanation 5

Note that numbers like 01 or 07 are not considered two-digit numbers.

见题面 Input 部分

见题面 Output 部分