Aminoàcids alienígenes T50529

Els científics de l’Observatori d’Intel·ligència Còsmica i Astrobiologia Transgalàctica (també conegut com OICAT) han obtingut mostres d’un meteorit que es pensa que podria contenir vida extraterrestre. En Roger, encarregat d’analitzar-les, ha descobert restes de cadenes amb una estructura semblant a l’ADN humà.

Mentre que l’ADN humà conté quatre bases diferents, representades amb les lletres ‘a’, ‘c’, ‘g’ i ‘t’, aquest ADN extraterrestre conté fins a 26 bases, que en Roger ha representat amb les lletres minúscules. De manera similar a l’ADN humà, que es divideix en triplets de bases consecutives (cadascun codificant un aminoàcid), en Roger intueix que la seqüència d’ADN extraterrestre es pot dividir en grups de lletres consecutives, cadascun corresponent a un aminoàcid alienígena.

Malauradament, no es coneix quins poden ser aquests aminoàcids. No obstant això, la seva companya de recerca, la Laia, ha descobert i ha anotat a la seva llibreta diversos parells de lletres que defineixen com comencen i acaben. Direm que una subparaula $s = s_1 \,\dots \,s_m$ és un aminoàcid vàlid si el parell $(s_1, s_m)$ es troba a la llibreta de la Laia. Una divisió d’una paraula en subparaules és vàlida si cada subparaula és un aminoàcid vàlid.

Per exemple, si la llibreta conté els parells $($‘a’, ‘c’$)$, $($‘b’, ‘g’$)$, $($‘b’, ‘b’$)$ i $($‘b’, ‘f’$)$, aleshores les úniques maneres vàlides de dividir la paraula “accbbbkppfcbdrtg” són:

acc-bbbkppfcbdrtg acc-b-bbkppfcbdrtg acc-bb-bkppfcbdrtg

acc-b-b-bkppfcbdrtg accbbbkppfc-bdrtg

En canvi, la separació acc-bbbkppfcb-drtg seria invàlida, perquè el parell $($‘d’, ‘g’$)$ no es troba a la llibreta.

Podeu calcular el nombre de maneres de dividir una paraula donada?

Entrada

L’entrada consisteix en diversos casos, cadascun amb una paraula amb lletres minúscules, seguida del nombre de parells $p \ge 1$, seguit dels $p$ parells, tots diferents. Podeu suposar que la paraula té entre 1 i $10^5$ lletres.

Sortida

Per a cada cas, escriviu el nombre de maneres de dividir la cadena d’ADN extraterrestre en aminoàcids vàlids. Com que la resposta pot ser molt gran, feu els càlculs mòdul $10^8 + 7$.

Puntuació

• Cas A:

  Casos on la paraula no té més de 100 lletres, com els de l’exemple d’entrada.

• Cas B:

  Casos de tot tipus.