그래서 순서가 뭔데?

Alice, Bob, Carol, Denise, Eddie, Frank는 지역 코미디 쇼에서 공연한다. 이들이 스탠드업 공연을 하는 순서는 아직 알려지지 않았다. 대신 다음과 같은 암호 같은 단서가 주어졌다 (A는 Alice, B는 Bob, C는 Carol, D는 Denise, E는 Eddie, F는 Frank를 뜻한다).

• A > B
• F < A
• not C D

첫 번째 단서는 A가 B보다 먼저 공연한다는 뜻이다. 두 번째 단서는 F가 A보다 나중에 공연한다는 뜻이다. 세 번째 단서는 C와 D가 연달아 공연하지 않는다는 뜻이다. (공연자를 숫자로 본다면, 부등호는 공연자가 큰 수부터 작은 수 순서로 정렬되어 있다고 가정한다.)

이 단서들을 따르는 순서 중 하나는 Alice, Carol, Bob, Denise, Frank, Eddie이다. 단서만으로 순서가 하나로 정해지지 않을 수 있으므로, 모든 단서를 만족하는 순서가 몇 가지인지 구한다.

첫 줄에는 공백으로 구분된 두 정수 $n$ ($2 \le n \le 10$)과 $c$ ($1 \le c \le 10$)가 주어진다. $n$은 공연자의 수이고, $c$는 단서의 개수이다. 공연자는 알파벳 대문자 앞쪽 $n$개 글자로 표시한다.

다음 $c$개 줄에는 단서가 한 줄에 하나씩 주어진다. 각 줄은 공백으로 구분된 세 값 $a$, $x$, $y$를 담는다 ($1 \le a \le 3$). $x$와 $y$는 서로 다른 대문자이며 앞쪽 $n$개 글자 중 하나이다. $a$는 제약의 종류를 나타낸다.

• $a = 1$이면 $x$의 공연이 $y$의 공연보다 먼저다.
• $a = 2$이면 $x$의 공연이 $y$의 공연보다 나중이다.
• $a = 3$이면 $x$와 $y$는 연달아 공연하지 않는다 (어느 순서든 상관없다).

단서끼리 모순되지 않으며, 조건을 만족하는 순서가 적어도 하나 존재함이 보장된다.

주어진 단서를 모두 만족하는 공연 순서의 개수를 출력한다.