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++