It is time for the star of the show: a very big cake of size (n \times n). Alice and her friends want to decorate the cake with whipped cream in the shape of snakes. Define a snake of size (k) as a path of size (k) that starts at one cell of the cake and only goes down or right. Due to her extensive study of cake, Alice knows that the best way to decorate this cake is to place (n) snakes where the (i)-th snake has a size of (2 \cdot i - 1). She has prepared all the whipping cream beforehand; however, some of her friends are too excited and have already started placing some snakes on the cake before Alice could plan how exactly to decorate the cake. Fortunately, Alice finds that it is still possible to decorate the cake. Help her find the number of ways she can decorate the cake without moving any snake her friends had placed. Since the number of possible ways might be big, output it under modulo (10^9 + 7). Two configurations are different if there exists a cell that is occupied by a different snake. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 1000)). The description of the test cases follows. The first line of each test case contains two integers (n) and (k) ((1 \le n \le 5000, 0 \le k \le n)) — the size of the cake and the number of snakes that her friends had placed, respectively. The next (2 \cdot k) lines contain information about the (k) placed snakes. Each set of two consecutive lines contains the information about one of the placed snakes in the following manner. The first line contains integer (s) ((1 \le s \le 2\cdot n-1), (s) is odd) — the size of the snake. The second line contains (r), (c) ((1 \le r,c\le n)) — its starting row, and its starting column. Then, a string of length (s - 1) consisting only of the letters R and D where R means the next cell is to the right of the current cell, and D means