Paraules amb a, b i c (2) P70046


Statement
 

pdf   zip

thehtml

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 pi ci, on pi és una posició entre 0 i n − 1, i ci és ‘a’, ‘b’ o ‘c’. Suposeu 1 ≤ n ≤ 104, 0 ≤ fn, i que totes les pi són diferents.

Sortida

Per a cada cas, escriviu el nombre de paraules que compleixen les restriccions mòdul 108 + 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
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++