SMS (2) P35938

0.70 Per enviar missatges de text amb els telèfons mòbils de principis dels 2000 s’havia de fer servir el teclat numèric, on cada tecla tenia associada més d’una lletra. Per exemple, la tecla 2 tenia associada les lletres a, b i c. Per indicar quina lletra es volia escriure, s’havia de prémer la tecla diverses vegades seguides. Així, prement 2 s’escrivia a, prement 22 s’escrivia b, i prement 222 s’escrivia c. A la dreta podeu veure quines lletres estaven assignades a cada número. Els espais s’escrivien prement un 0.

0.28

Donades les tecles premudes, podeu calcular a quants texts originals poden correspondre? Per exemple, 33 es podria correspondre tant a dd com a e.

Entrada

L’entrada consisteix en diverses línies, cadascuna amb un text no buit amb fins a $10^4$ dígits, però sense uns.

Sortida

Per a cada línia de l’entrada, escriviu el nombre de texts que s’hi corresponen. Com que el resultat pot ser molt gros, feu els càlculs mòdul $10^8 + 7$.