Words with a, b and c (2) P70046

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 \le n \le 10^4$, $0 \le f \le 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$.