What's the Order Anyway?

Alice, Bob, Carol, Denise, Eddie and Frank are performing in a local comedy show. Their stand-up routine order is not known. Instead, you have these cryptic clues (A is Alice, B is Bob, C is Carol, D is Denise, E is Eddie and F is Frank):

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

The first clue means that A performs before B. The second clue means that F performs after A. The third clue means that C and D do not perform consecutively. (If the acts are treated as numbers, the inequality signs assume the acts are sorted from greatest to least.)

Given these clues, one possible order is Alice, Carol, Bob, Denise, Frank, Eddie. The exact order may not be fixed by the clues, so the task is to count how many orders satisfy all of them.

The first line contains two space-separated integers $n$ ($2 \le n \le 10$) and $c$ ($1 \le c \le 10$). Here $n$ is the number of comedy acts and $c$ is the number of clues. The acts are denoted by the first $n$ uppercase letters.

Each of the next $c$ lines contains a clue as three space-separated values $a$, $x$, and $y$, where $1 \le a \le 3$. The letters $x$ and $y$ are distinct uppercase letters among the first $n$ letters. The value $a$ gives the type of restriction:

• $a = 1$: the act of $x$ comes before the act of $y$.
• $a = 2$: the act of $x$ comes after the act of $y$.
• $a = 3$: the acts of $x$ and $y$ do not occur consecutively, in either order.

The clues are not contradictory, and at least one valid ordering exists.

Print the number of different orders of the comedy acts that satisfy all the clues.