画线 - 题目

Busy Beaver 喜欢在纸上画线。然而，当两条线相交时，他会感到难过。一天晚上，他梦见了一幅由许多射线组成的杰作，且这些射线互不相交。但是，当他醒来时，他只记得射线是从哪里出发的，却不记得它们朝哪个方向延伸！请帮他重现这幅画。

形式化地说，给定平面上的 $N$ 个点，每个点的 $x$ 和 $y$ 坐标均为 $[1, N]$ 范围内的不同整数。每个点被标记为 UD 或 LR。对于每个 UD 点，你必须从该点出发画一条垂直向上或向下的无限长射线。同样，对于每个 LR 点，你必须从该点出发画一条水平向左或向右的无限长射线。

在所有 $2^N$ 种为每个点分配方向的方式中，判断是否存在一种分配方式使得没有两条射线相交，如果存在，输出满足条件的分配方案数，对 $10^9 + 7$ 取模。

为了方便起见，我们保证如果 $x$ 是满足条件的分配方案数且 $x > 0$，则 $x \not\equiv 0 \pmod{10^9 + 7}$。

每个测试包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

每个测试用例的第一行包含一个正整数 $N$ ($1 \le N \le 10^3$)，表示点的数量。

接下来的 $N$ 行中，第 $i$ 行包含两个整数 $x_i, y_i$ 和一个字符串 $s_i$，其中 $(x_i, y_i)$ 表示第 $i$ 个点的位置，$s_i \in \{\text{UD}, \text{LR}\}$ 表示该点允许的射线方向。

保证 $x_i$ 是 $[1, N]$ 范围内两两不同的整数，$y_i$ 也同样满足此条件。

保证所有测试用例的 $N$ 之和不超过 $10^4$。

对于每个测试用例，输出两行。

第一行输出 “YES” 或 “NO”，表示是否存在满足条件的分配方案。你可以以任何大小写形式输出答案。例如，“yEs”、“yes”、“Yes” 和 “YES” 都会被识别为肯定回答。

第二行输出满足条件的分配方案数，对 $10^9 + 7$ 取模。

如果你正确回答了 YES/NO，但满足条件的分配方案数计算错误，你将获得每个子任务 50% 的分数。

3
2
1 1 UD
2 2 UD
2
1 2 UD
2 1 LR
7
1 5 UD
2 3 UD
3 4 LR
4 1 LR
5 7 LR
6 2 UD
7 6 UD

YES
4
YES
3
NO
0

在第一个测试用例中，任何 $2^2 = 4$ 种分配方式都不会导致相交。

在第二个测试用例中，如果第一个点被分配为 D，第二个点被分配为 L，则两条射线会在 $(1, 1)$ 处相交。其他 3 种分配方式均可行。

在第三个测试用例中，所有分配方式都会导致至少一次相交。

第二个测试用例的示意图如下：

QOJ.ac