기차

꼬마 야쿠시는 엄마에게서 $n$개의 객차로 이루어진 장난감 기차를 받았습니다. 각 객차의 뒷면에는 영어 소문자로 이루어진 일련번호가 적혀 있습니다.

야쿠시는 이 $n$개의 객차를 원하는 순서로 늘어놓아 기차를 만들 수 있습니다(항상 $n$개의 객차를 모두 사용합니다). 객차들의 일련번호를 왼쪽부터 차례로 이어 읽으면 하나의 문자열 $w$가 만들어집니다.

야쿠시는 엄마에게 종이에 문자열 $t$를 적어 달라고 했습니다. 그는 각 순서로 만든 문자열 $w$를 패턴으로 삼아 $t$ 안에서 찾으려고 합니다. 객차를 늘어놓는 모든 $n!$가지 순서에 대해, 그 순서로 만든 패턴 $w$가 $t$에 나타나는 횟수를 모두 더한 값을 구하세요.

서로 다른 시작 위치라면 겹쳐서 나타나도 각각 한 번씩 셉니다. 객차는 서로 다른 물체이므로, 일련번호가 같은 객차가 있더라도 각 순서(순열)는 따로 셉니다.

첫째 줄에 정수 $n$ ($1 \le n < 10$)이 주어집니다. 이어지는 $n$개의 줄에는 $i$번째 객차의 일련번호 $w_i$가 주어지며, 각 일련번호는 길이가 $10^5$ 이하인 비어 있지 않은 영어 소문자 문자열입니다. 그다음 줄에는 문자열 $t$가 주어지며, 길이는 $10^6$ 이하인 영어 소문자 문자열입니다.

모든 $n!$가지 순서로 만든 패턴들이 $t$에 나타나는 횟수의 총합을 정수 하나로 출력하세요.