题目描述

派对的主角是一块 $n\times n$ 的大蛋糕。Alice 和朋友们想在蛋糕上用奶油摆出蛇形图案。

一条大小为 $k$ 的蛇是一条包含 $k$ 个格子的路径，从某个格子出发，每一步只能向下或向右走。

Alice 知道最好的装饰方式是放置 $n$ 条蛇，其中第 $i$ 条蛇大小为 $2i-1$。不过有些朋友太兴奋，已经提前在蛋糕上放了一些蛇。保证仍然存在至少一种完整装饰方式。

请你计算在不移动已放置蛇的前提下，Alice 有多少种方式完成装饰。两个方案不同，当且仅当存在某个格子被不同编号的蛇占据。

答案对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组测试数据第一行包含两个整数 $n,k$，表示蛋糕大小和已经放置的蛇的数量。

接下来 $2k$ 行描述这 $k$ 条蛇。每条蛇用两行描述：

第一行一个奇数 $s$，表示蛇的大小。

第二行包含起点行列 $r,c$。若 $s>1$，后面还会有一个长度为 $s-1$ 的字符串，只包含 R 和 D，分别表示向右和向下。若 $s=1$，则没有这个字符串。

输出格式

对于每组测试数据，输出一种完整装饰方式数量对 $10^9+7$ 取模后的结果。

数据范围

• $1 \le t \le 1000$
• $1 \le n \le 5000$
• $0 \le k \le n$
• $1 \le s \le 2n-1$，且 $s$ 为奇数
• 已给出的蛇互不重叠、大小互不相同，且都在蛋糕边界内
• 每组答案保证非零
• 所有测试数据的 $n$ 之和不超过 $5000$，所有给定蛇长之和不超过 $4\cdot 10^5$

5
3 1
5
1 1 RDRD
4 1
1
3 2
3 1
5
1 1 RRDD
3 1
3
2 1 DR
4567 0

1
6
2
2
833729690

提示

观察从左下到右上的反对角线，可以把蛇形摆放与一个 $1\ldots n$ 的排列建立双射。已放置的蛇给出了这些排列元素之间的相对限制。

来源

Codeforces Round 2232 E - Snaking Arrangement