Misopan si Trofonaced s-au intalnit in sfarsit si au de descifrat un mesaj. Fiecare dintre ei are cate un sir de caractere format din cifre si litere mici (de la a la z). Literele care apar corespund unor variabile (prima variabila e notata cu a, a doua cu b etc). Pentru fiecare variabila se cunoaste o lungime L_i si o baza de numeratie B_i. Astfel valoarea unei variabile poate fi orice numar cu exact L_i cifre intre 0 si B_i-1 (si prima cifra poate fi 0). Vom numi sir expandat un sir in care literele sunt inlocuite cu valorile variabilelor corespunzatoare. Mesajul pe care cei doi il cauta este obtinut prin gasirea unor valori pentru variabile astfel incat expandand ambele siruri rezulta acelasi sir de cifre.

Date de intrare

Prima linie a fisierului siruri.in contine un numar intreg N reprezentand numarul de variabile. Urmatoarele N linii contin cate doua numere intregi L_i si B_i (lungimile si bazele variabilelor). Urmatoarele doua linii contin primul si respectiv al doilea sir.

Date de iesire

Fisierul de iesire siruri.out va contine o linie pe care se va afla numarul de posibilitati.

• 0 <= N <= 26
• Sirurile date vor contine numai cifre si primele N litere mici
• Lungimea sirurilor expandate nu va depasi 16000
• 2 <= B_i <= 10
• Toate cele N variabile vor fi folosite in sirurile date

Timp maxim de executie/test: 1 secunda.