Prologin

DIFFICULTE

LIMITE DE MEMOIRE

100000 ko

LIMITE DE TEMPS

1000 ms

Dans ce problème, une séquence d'ADN est une suite finie de lettre dans l'ensemble {A,T,G,C}. Chaque lettre sera appelé un nucléotide.

Un biologiste dispose d'une séquence d'ADN s de longueur N dont il ne connait pas l'agencement des nucléotides. L'opération qui consiste à découvrir la suite des nucléotide est le séquençage. Pour séquencer son brin d'ADN, le biologiste fabrique physiquement plusieurs copies de s. Toutes ces copies sont ensuite placées dans une machine, qui les casse aléatoirement en petits morceaux plus facilement reconnaissables. Enfin, la machine renvoie la séquence exacte de certains de ces petits morceaux. Le but de ce problème est de calculer combien de séquences s sont possibles, sachant que s est de longueur N, et en connaissant les données renvoyées par la machine.

Prenons un exemple. La séquence initiale (mais qui nous est inconnue) est TAAACG. La machine en fait plusieurs copies, et morcelle chacune de celles-ci comme suit :

• TAAACG -> TA, AA, CG
• TAAACG -> T, AAAC, G
• TAAACG -> T, AA, AACG

Ensuite, la machine lit certains de ces morceaux (pas nécessairement dans le bon sens !). Imaginons qu'elle renvoie les morceaux suivants : AT, AACG (remarquez que le premier morceau est inversé). Alors 22 chaines de longueur 5 sont possibles: AACGAT AACGTA ATAACG ATGCAA AGCAAT TAAACG TAACGA TAACGT TAACGG TAACGC TAGCAA TTAACG TGCAAT GTAACG GGCAAT GCAAAT GCAATA GCAATT GCAATG GCAATC CTAACG CGCAAT

Remarquez que toutes ces chaînes contiennent AT et AACG, dans un sens ou dans l'autre, et se chevauchant éventuellement.

• Sur la première ligne : l'entier N (entre 1 et 25, bornes incluses)
• Sur la deuxième ligne : l'entier M (entre 1 et 7, bornes incluses)
• Sur les M prochaines lignes, les morceaux d'ADN tels que lus par la machine.

Un entier, le nombre de chaînes initiales possibles.

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

6
2
AT
AACG

22

Exemple 2
en entrée ...

7
2
AT
AACG

162