Un pattern di dimensione n è una stringa di lunghezza n i cui caratteri sono elementi del seguente insieme {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,a, b, c, d, e, f, g, ?}.
I pattern sono trasformati in stringhe usando le seguenti regole:
- i simboli da 0 a 9 possono essere trasformati solo in se stessi;
- il simbolo a può essere trasformato in uno dei simboli 0, 1, 2, 3;
- il simbolo b può essere trasformato in uno dei simboli 1, 2, 3, 4;
- il simbolo c può essere trasformato in uno dei simboli 2, 3, 4, 5;
- il simbolo d può essere trasformato in uno dei simboli 3, 4, 5, 6;
- il simbolo e può essere trasformato in uno dei simboli 4, 5, 6, 7;
- il simbolo f può essere trasformato in uno dei simboli 5, 6, 7, 8;
- il simbolo g può essere trasformato in uno dei simboli 6, 7, 8, 9;
- il simbolo ? può essere trasformato in uno dei simboli da 0 a 9.
Sono assegnati due pattern p1 e p2 e siano S1 e S2 gli insiemi di stringhe che possono essere ottenuti, rispettivamente da p1 e p2, usando le regole di trasformazione sopra definite.
Si deve trovare il numero di stringhe che appartengono alla intersezione di S1 e S2.
Dati di input
La prima riga del file di input contiene il pattern p1 e la seconda riga contiene p2.
I due pattern hanno la medesima dimensione n, 0 < n < 10.
Dati di output
Contiene il numero che rappresenta la soluzione del problema.
Esempi
| input.txt | output.txt | |
|---|---|---|
| 1 | ??? abc |
64 |
| 2 | ?a? 000 |
1 |
Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.