{"raw_statement":[{"iden":"statement","content":"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.\n\nYour 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).\n\nA valid pattern has the following properties: \n\nUnfortunately 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.\n\nThe 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.\n\nIf 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.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input1 0Output34Input2 101 11 21 32 12 22 32 43 23 33 4OutputBAD MEMORYInput1 31 42 43 4Output24"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = \\{ (x,y) \\mid x \\in \\{1,2,3\\}, y \\in \\{1,2,3,4\\} \\} $ be the set of 12 grid points.  \nLet $ S \\subseteq G $ with $ |S| = N $ be the set of points **excluded** from the pattern.  \nLet $ R = G \\setminus S $ be the set of **available** points.  \n\nA **pattern** is a sequence $ P = (p_1, p_2, \\dots, p_L) $ where $ p_i \\in R $, such that:  \n- All consecutive points $ p_i, p_{i+1} $ are connected by a straight line segment.  \n- 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\").  \n- No point is repeated: $ p_i \\ne p_j $ for all $ i \\ne j $.  \n\n**Constraints**  \n1. $ 1 \\le L \\le 1000 $  \n2. $ 0 \\le N \\le 12 $  \n3. $ S \\subseteq G $, $ |S| = N $, all points in $ S $ are distinct.  \n4. $ L \\le |R| = 12 - N $ (since no repetition is allowed).  \n\n**Objective**  \nCount the number of valid patterns $ P $ of length $ L $ over the available set $ R $, satisfying the connectivity and no-repetition constraints.  \nIf the count is zero, output `\"BAD MEMORY\"`. Otherwise, output the count.","simple_statement":"You have a 3x4 grid of points (3 columns, 4 rows).  \nYou need to count how many valid pattern paths of exactly length L exist, avoiding N forbidden points.  \n\nA valid path:  \n- Moves between points (horizontally, vertically, or diagonally).  \n- Can’t skip over an unvisited point in between (like in Android lock patterns).  \n- Each point can be visited only once.  \n- Length L = number of line segments (so path has L+1 points).  \n\nYou’re given L and N forbidden points.  \nFind total number of such paths.  \nIf none, print \"BAD MEMORY\".","has_page_source":false}