Paraules amb a, b i c (2) P70046

Statement

html

En aquest problema considerem paraules de mida n, formades només amb les lletres ‘a’, ‘b’ i ‘c’, i sense dues o més lletres iguals consecutives. Suposeu que algunes posicions de la paraula tenen fixada la seva lletra. Feu un programa que compti totes les paraules que compleixen totes aquestes restriccions.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, seguit del nombre de posicions fixades f, seguit de f parells p_i c_i, on p_i és una posició entre 0 i n − 1, i c_i és ‘a’, ‘b’ o ‘c’. Suposeu 1 ≤ n ≤ 10⁴, 0 ≤ f ≤ n, i que totes les p_i són diferents.

Sortida

Per a cada cas, escriviu el nombre de paraules que compleixen les restriccions mòdul 10⁸ + 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

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: C++
User solutions: C++