CF2232E Snaking Arrangement

现在到了重头戏的时刻：一个很大的 $n \times n$ 的蛋糕。 Alice 和她的朋友们想用奶油在蛋糕上装饰成“蛇”的形状。定义大小为 $k$ 的蛇为一条从蛋糕的某个格子出发的长度为 $k$ 的路径，每一步只能向右或向下。 经过对蛋糕的深入研究，Alice 认为给这个蛋糕装饰的最佳方式是放置 $n$ 条蛇，其中第 $i$ 条蛇的长度为 $2 \cdot i - 1$。她已经提前准备好了所有的奶油蛇；但有些朋友太兴奋，已经在 Alice 还没规划好如何装饰蛋糕之前随意放置了一些蛇。 幸运的是，Alice 发现仍然可以完成装饰。请你帮助她计算可以在不移动任何她朋友已经放好的蛇的情况下装饰蛋糕的方案数。由于结果可能很大，请对 $10^9 + 7$ 取模后输出。 如果存在某个格子被不同的蛇占据，则认为两个方案是不同的。

每组测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 1000$）。接下来是各个测试用例的描述。 每个测试用例的第一行为两个整数 $n$ 和 $k$（$1 \le n \le 5000, 0 \le k \le n$），分别表示蛋糕的边长和她朋友预先放置的蛇的数量。 接下来的 $2 \cdot k$ 行描述了这 $k$ 条已放置的蛇。每两行描述一条蛇，格式如下： 第一行是一个整数 $s$（$1 \le s \le 2\cdot n - 1$，且 $s$ 为奇数），表示当前蛇的长度。 第二行为 $r, c$（$1 \le r, c \le n$），以及一段长度为 $s-1$ 只包含字母 R 和 D 的字符串，表示蛇的起始行、起始列，以及蛇走的路径。R 表示蛇下一格向右，D 表示蛇下一格向下。若 $s=1$，该字符串为空。 保证不存在两条蛇重叠、长度相同，且所有蛇均处于蛋糕边界内。 保证每个测试用例都有非零答案。 $ \displaystyle \sum n \le 5000 $ 且 $ \displaystyle \sum s \le 4 \times 10 ^ 5 $。

对于每组测试用例，输出一个整数，表示 Alice 能够装饰蛋糕的方案数，对 $10^9 + 7$ 取模。

在第一个测试用例中，唯一的装饰方法如下所示：  在第二个测试用例中，两种可能的装饰方法如下所示：   由 ChatGPT 5 翻译