One of the ways to lock some phones, is the lock pattern. To unlock your phone you have to draw a secret pattern on a grid of some points, the pattern will be some line segments connecting these points.
Your phone pattern grid consists of four rows with three points in each row. The following image on the left is the representation of the grid, it can be modeled as a 2D plane with *X* and *Y* coordinates for each point, for example the top left point is (1,4) and the bottom right point is (3,1). The image on the right is a valid pattern, which connects the following points in this order: (3,4) (2,4) (1,2) (2,1) (2,2) (3,2) (3,1) (1,3).
A valid pattern has the following properties:
Unfortunately you forgot your phone's pattern, but you remember the length of the pattern and a set of points *S* which are not touched by the pattern for sure (the points which are not in *S* might and might not be touched by the pattern), and you decided to try all the valid patterns which satisfy what you remember. Before doing this, you have to write a program to calculate for you the number of different valid patterns.
The first line of the input contains two integers *L* and *N* separated by a single space. *L* (1 ≤ *L* ≤ 1,000) is the length of the pattern (as described above), and *N* (0 ≤ *N* ≤ 12) is the number of points that you are sure they are not touched by the pattern, followed by *N* lines each line contains two integers *X* (1 ≤ *X* ≤ 3) and *Y* (1 ≤ *Y* ≤ 4) separated by a single space, representing the coordinates of one of the points which are not touched by the pattern for sure, the *N* points are distinct.
If there are no valid patterns according to what you remember, print on a single line "BAD MEMORY" (without the quotes), otherwise print the number of different valid patterns.
## Input
The first line of the input contains two integers *L* and *N* separated by a single space. *L* (1 ≤ *L* ≤ 1,000) is the length of the pattern (as described above), and *N* (0 ≤ *N* ≤ 12) is the number of points that you are sure they are not touched by the pattern, followed by *N* lines each line contains two integers *X* (1 ≤ *X* ≤ 3) and *Y* (1 ≤ *Y* ≤ 4) separated by a single space, representing the coordinates of one of the points which are not touched by the pattern for sure, the *N* points are distinct.
## Output
If there are no valid patterns according to what you remember, print on a single line "BAD MEMORY" (without the quotes), otherwise print the number of different valid patterns.
[samples]
**Definitions**
Let $ G = \{ (x,y) \mid x \in \{1,2,3\}, y \in \{1,2,3,4\} \} $ be the set of 12 grid points.
Let $ S \subseteq G $ with $ |S| = N $ be the set of points **excluded** from the pattern.
Let $ R = G \setminus S $ be the set of **available** points.
A **pattern** is a sequence $ P = (p_1, p_2, \dots, p_L) $ where $ p_i \in R $, such that:
- All consecutive points $ p_i, p_{i+1} $ are connected by a straight line segment.
- For any two consecutive points $ p_i = (x_1,y_1) $, $ p_{i+1} = (x_2,y_2) $, if the line segment between them passes through any other grid point $ q \in G \setminus \{p_i, p_{i+1}\} $, then $ q \in S $ (i.e., the intermediate point is excluded and thus allowed to be "jumped over").
- No point is repeated: $ p_i \ne p_j $ for all $ i \ne j $.
**Constraints**
1. $ 1 \le L \le 1000 $
2. $ 0 \le N \le 12 $
3. $ S \subseteq G $, $ |S| = N $, all points in $ S $ are distinct.
4. $ L \le |R| = 12 - N $ (since no repetition is allowed).
**Objective**
Count the number of valid patterns $ P $ of length $ L $ over the available set $ R $, satisfying the connectivity and no-repetition constraints.
If the count is zero, output `"BAD MEMORY"`. Otherwise, output the count.