Bilda ord

Time limit1sMemory limit1024 MB

Summary

Count permutations of N distinct letters that satisfy rules forcing a letter into given positions or requiring one letter to come immediately before another.

Level: Medium6 of 10
Topics: Backtracking, Combinatorics, Implementation, Bit manipulation
Solved: No attempts yet

Problem

Fatimeh is studying her native language, which uses the Arabic alphabet. Right now she is working on an exercise where she has to answer how many ways she can form a word from the given letters.

If the exercise had been in Swedish, it could look like this:

r M e a

Since four letters are given, Fatimeh knows she has to test $4\*3\*2\*1 = 24$ permutations. But because the letter M is "large", we know it must be placed at the beginning of the word. With that condition, only $6$ words can be formed, for example $Mera$ , but not $raMe$ . The Arabic alphabet does not have uppercase and lowercase letters in the same way, but it has other rules about where in the word a letter may appear, including in relation to other letters.

In this problem we assume there are two types of restrictions: either a letter must come immediately before another letter, or a letter may only stand in certain positions. Examples of these rules and the notation we use are in the following table:

Rule	Notation
Letter $B$ must stand in position $1$ or position $4$	`B@01,04`
Letter $D$ must immediately precede $C$ or $B$	`D:CB`

Write a program that computes in how many ways $N$ different letters (called A, B, C,... etc. for simplicity) can be placed, given a number of rules of these two types.

Input

The first line contains two integers, the number of letters $N$ and the number of rules $K$ . Then follow $K$ lines, each describing one rule according to the notation above. A given letter cannot appear first in more than one rule of each type. Note that all position numbers are written with two digits.

Output

The program shall print one integer: the number of ways the letters can be placed. The answer will always be less than 10 million.

Constraints

$2\le N\le 15$

Examples4

Example 1
Input
```
4 2
B@01,04
D:CB
```
Expected output
```
6
```
Example 2
Input
```
3 2
B@02
A:BC
```
Expected output
```
1
```
Example 3
Input
```
3 2
B@02
A:C
```
Expected output
```
0
```

Example 4

Input

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

Expected output