Enunț

Ema este foarte pasionată de șiruri de caractere. Pentru că îi este prea greu să le numească “șiruri de caractere”, ea s-a gândit să le denumească “stringuri”, cu singularul “string”. Într-o zi ea a descoperit 2 seturi formate fiecare din N stringuri. Ema spune că un string X este prieten cu un string Y dacă X se regăsește ca subsecvență în Y. De exemplu, pentru X = "ana" și Y = "pana", X este prieten cu Y. De asemenea ea definește proprietatea de super prietenie între două seturi de stringuri S1 și S2 de lungime N astfel: pentru orice i (1 ≤ i ≤ N) S1[i] este prieten cu S2[i].

Cerința

Acum ea își pune următoarea problemă: “Având cele 2 seturi de stringuri S1 și S2, în câte moduri pot permuta setul S1 astfel încât proprietatea de super prietenie între S1 și S2 să nu se respecte ?”. Emei i s-a părut prea ușoară problema, așa că te provoacă și pe tine să o rezolvi.

Date de intrare

Fișierul de intrare matching.in conține pe prima linie numărul N, următoarele N linii se vor afla câte două stringuri separate prin spațiu, primul aparținând lui S1, cel de-al doilea lui S2.

Date de ieșire

Fișierul de ieșire matching.out va conține pe prima linie numărul S, reprezentând soluția problemei puse de Ema.

Restricții și precizări

• 1 ≤ N ≤ 15
• Stringurile din S1 sunt distincte
• 1 ≤ lungimea unui string ≤ 500

Exemplu:

matching.in

4
abcd abcdfdeefc
fd abcdfdeefcadd
eefc fdeefcabcdadd
add faddabcdaddeefcfd

matching.out

6