단어 만들기

Fatimeh는 아랍 문자를 사용하는 자신의 모어를 공부하고 있다. 지금 그녀는 문제에 주어진 글자들로 단어를 만들 수 있는 방법의 수를 답하는 연습 문제를 풀고 있다.

이를 스웨덴어로 나타내면 연습 문제는 다음과 같을 수 있다:

r M e a

네 글자가 주어졌으므로 Fatimeh는 $4*3*2*1 = 24$개의 순열을 확인해야 한다는 것을 안다. 하지만 글자 M은 ``대문자''이므로 단어의 맨 앞에 놓여야 한다. 이 조건에서는 $6$개의 단어만 만들 수 있으며, 예를 들면 $Mera$은 가능하지만 $raMe$은 불가능하다. 아랍 문자에는 같은 방식의 대문자와 소문자가 없지만, 글자가 단어의 어느 위치에 올 수 있는지와 다른 글자들과의 관계에 관한 다른 규칙들이 있다.

이 문제에서는 두 종류의 제약 조건이 있다고 가정한다. 하나는 어떤 글자가 다른 특정 글자의 바로 앞에 와야 한다는 것이고, 다른 하나는 어떤 글자가 특정 위치들에만 올 수 있다는 것이다. 이러한 규칙의 예와 이 문제에서 사용하는 표기법은 다음 표에 나와 있다:

규칙 | 표기법

글자 $B$는 위치 $1$ 또는 위치 $4$에 있어야 한다 | B@01,04

글자 $D$는 $C$ 또는 $B$의 바로 앞에 와야 한다 | D:CB

이 두 종류의 규칙들이 주어질 때, $N$개의 서로 다른 글자(편의를 위해 A, B, C,... 등으로 부른다)를 배치하는 방법의 수를 계산하는 프로그램을 작성한다.

채점

$60$점 상당의 테스트 케이스에서는 $2\le N\le 9$가 성립한다. 만점 ($100$점)을 받으려면 프로그램이 $2\le N\le 15$을 처리할 수 있어야 한다. 모든 경우에 $1\le K\le N$가 성립한다. $N$이 큰 경우 제약 조건은 글자들 사이에 거의 균등하게 분포한다.

첫째 줄에 글자의 수 $N$과 규칙의 수 $K$을 나타내는 두 정수가 주어진다. 이어지는 $K$개의 줄에는 각각 위 표기법에 따라 하나의 규칙이 주어진다. 각 종류의 규칙에서 특정 글자가 규칙의 맨 앞에 등장하는 경우는 최대 하나이다. 모든 위치 번호는 두 자리 숫자로 표기된다는 점에 유의한다.

글자들을 배치하는 방법의 수를 나타내는 정수 하나를 출력한다. 답은 항상 10백만 미만이다.

만들 수 있는 단어는 ACDB, ADCB, BADC, CADB, DCAB, BDCA이다.