In this problem we consider words of size n made up only of letters ‘a’, ‘b’ and ‘c’, and without two or more consecutive equal letters. Suppose that some positions of the word have fixed letters. Write a program to count all the words that meet these constraints.

Input

Input consists of several cases.
Every case starts with n,
followed by the number of fixed positions f,
followed by f pairs p_{i} c_{i},
where p_{i} is a position between 0 and n − 1
and c_{i} is ‘a’, ‘b’ or ‘c’.
Suppose 1 ≤ n ≤ 10^{4},
0 ≤ f ≤ n,
and that all p_{i}’s are different.

Output

For every case,
print the number of words that satisfy the constraints
modulo 10^{8} + 7.

Public test cases

**Input**

2 0 3 1 2 b 1 1 0 a 2 2 0 b 1 b 4 2 3 a 0 a 10000 0 27 0

**Output**

6 4 1 0 2 15429856 1326578

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++