Problem H
Pandemic Shopping

Image by Arsenii Palivoda (Shutterstock); Used under license

In response to the COVID-19 pandemic, most retail stores instituted a variety of restrictions on customer behaviour in order to comply with government social/physical distancing rules. In particular, many stores placed arrow markers on aisle floors to direct the flow of customer traffic, in essence turning the floor plan into a directed graph. This was reasonably effective in most cases, but it did introduce some strange possibilities if arrows were not laid down correctly, for example, not being able to access all products in all aisles, or perhaps getting trapped in a cycle and never being able to leave the store.

Tony is the nighttime manager for his town’s franchise of the famous MAPS grocery chain. (The official name of the company, after its late founder, is Murgatroyd Algernon Prufrock Scrooge, Ltd., but for some reason customers prefer MAPS.) When Tony arrives for his shift, he notices that not all aisles have arrows. The instructions left by the daytime manager stipulate that his main task for the night is to choose directions for the remaining aisles, and then lay down the corresponding arrows. While sipping his first coffee, Tony begins to wonder how many ways he can complete this task, assuming, of course, that shoppers need to be able to enter the store, access any products they want, and then exit the store.

The MAPS floor plan is very simple:

• The store is rectangular, and has a north-south/east-west orientation.

• There is a north-south aisle called Aisle A running the full length of the west side of the store, and another north-south aisle called Aisle B running the full length of the east side of the store.

• There are $n$ east-west aisles numbered $1, 2, \ldots , n$, each of which connects Aisle A to Aisle B. These are numbered consecutively from south to north — Aisle $1$ runs the length of the south end of the store, and Aisle $n$ runs the length of the north end of the store.

• There is an entrance/exit at the south-west corner of the store, and another at the north-east corner of the store.

Every product is located somewhere along one of the $n$ east-west aisles, hence these are called product aisles; aisles A and B are called access aisles. A shopper must be able to travel the full length of every product aisle at least once during a visit to the store. After an aisle has been assigned a direction (and marked with a corresponding arrow), customer traffic along that aisle is strictly one-way in the indicated direction.

Given the information left for Tony by the daytime manager, help him determine how many ways he can complete his task. As an example, the figure below is an illustration of Sample Input $1$.

Figure 1: Illustration of Sample Input $1$

Input

The input specifies a single test case. The first line of input contains two space-separated integers, $n$ and $k$, where $n$ is the number of product aisles $(2 \leq n \leq 30)$, and $k$ is the number of aisles that have been assigned directions prior to Tony’s shift $(0 \leq k < (n+2))$. This is followed by $k$ lines, each of which contains two space-separated tokens, <id> and <dir>, where <id> is an aisle identifier, and <dir> is the direction assigned to that aisle. The value of <id> is A, B, or an integer in the interval $[1,n]$. If <id> is A or B, then <dir> is either N2S (north to south) or S2N (south to north). If <id> is an integer, then <dir> is either E2W (east to west) or W2E (west to east). All $k$ <id> values are distinct.

Output

Output a line containing a single integer: the number of ways Tony can complete his task, as described above.

5 4
A S2N
B S2N
5 W2E
2 E2W

1