단어 만들기

시간 제한1초메모리 제한1024 MB

요약

N개의 서로 다른 글자를 나열할 때, 특정 위치 제한과 특정 글자 바로 뒤에 와야 하는 제한을 모두 만족하는 순열의 수를 센다.

난이도: 보통10점 중 6점
유형: 백트래킹, 조합론, 구현, 비트 연산
정답자: 아직 제출이 없습니다

문제

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,... 등으로 부른다)를 이러한 두 종류의 규칙이 여러 개 주어졌을 때 배치할 수 있는 방법의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 글자의 수 $N$ 과 규칙의 수 $K$ 가 주어진다. 이어서 $K$ 개의 줄에 각각 위의 표기법에 따라 규칙이 하나씩 주어진다. 어떤 글자도 같은 종류의 규칙에서 맨 앞에 두 번 이상 나오지 않는다. 모든 위치 번호는 두 자리로 쓰인다.

출력

프로그램은 글자들을 배치할 수 있는 방법의 수를 정수로 출력한다. 답은 항상 1000만 미만이다.

제한

$2\le N\le 15$

예제4

예제 1
입력
```
4 2
B@01,04
D:CB
```
예상 출력
```
6
```
예제 2
입력
```
3 2
B@02
A:BC
```
예상 출력
```
1
```
예제 3
입력
```
3 2
B@02
A:C
```
예상 출력
```
0
```

예제 4

입력

8 4
E@02,08,05
A:CEF
A@05,02,03
C:ABCDH

예상 출력