문제
K개의 알파벳과 빈칸이 적힌 타일이 주어지고, 이를 가지고 단어를 만들려고 한다. 각 타일은 한 번씩만 사용할 수 있으며, 빈칸에는 어떤 알파벳을 적어도 상관없다.
N개의 단어로 구성된 사전이 주어졌을 때, 타일로 만들 수 있는 사전에 들어있는 단어의 수를 알아내는 프로그램을 작성하라.
주의 : 한 번에 사전의 단어를 만드는 것이 아닌, 각 단어에 대해서 타일을 사용하는 것이다.
입력
첫 번째 줄에는 N이 입력된다. N은 1,000이하의 정수이다. 그 다음 줄에는 N개의 사전에 적힌 단어가 한 줄에 하나씩 입력된다. 단어는 알파벳 대문자로 표기되며, 길이는 1이상 7이하이다. 마지막 줄에는 사용할 수 있는 타일에 적힌 알파벳 대문자들이 입력된다. 빈칸의 경우 '_'(따옴표 제외)로 표기된다. 타일의 최대 개수는 7이다.
출력
타일을 이용해 만들 수 있는 사전의 단어의 개수를 출력한다.
예제 #1
5
PROGRAM
CONTEST
PIZZA
ZA
PITA
_PIZA
3
예제 #2
3
BANANAS
CARROTS
FIGS
A__AA__
2
로그인해야 코드를 작성할 수 있어요.