26084번 - DPS

ICPC는 세 명이 한 팀을 이뤄 참가하는 국제 대학생 프로그래밍 대회이다. ICPC에 참가하는 각 팀의 이름은 세 팀원의 핸들 첫 글자를 임의의 순서로 이어 붙인 것이다. 핸들이란 Baekjoon Online Judge와 같은 온라인 채점 사이트에서 사용하는 고유한 ID이다.

예를 들어 핸들이 각각 DONGGAS, PICASSO, SEMTEO인 세 명으로 이루어진 팀의 이름은 DPS, DSP, PDS, PSD, SDP, SPD 중 하나이다. 또, 핸들이 각각 RAARARAARA, WBCHO, WEASEL인 세 명으로 이루어진 팀의 이름은 RWW, WRW, WWR 중 하나이다.

팀 이름 $S$와 $N$명의 핸들이 주어지면, $N$명으로 팀 $S$를 구성하는 모든 경우의 수를 구해보자.

첫째 줄에 팀 이름 $S$가 주어진다. 팀 이름 $S$는 영어 대문자 3개로 이루어져 있다.

둘째 줄에 사람의 수를 나타내는 양의 정수 $N$($3 \le N \le 50\,000$)이 주어진다.

셋째 줄부터 $N$명의 핸들이 한 줄에 하나씩 주어진다. 각 핸들의 길이는 1이상 10이하이다.

모든 사람의 핸들은 영어 대문자로만 이루어진 공백이 없는 문자열이다. 또, 모든 사람의 핸들은 서로 다르다.

첫째 줄에 팀 $S$의 구성으로 가능한 모든 경우의 수를 출력한다.

출력이 32비트 정수형 타입의 표현 범위를 초과할 수 있으므로 언어에 따라 아래와 같은 적절한 64비트 정수형 타입을 이용하여 출력해야 한다.

• C/C++: long long
• JAVA: long
• Kotlin: Long