点集划分

度度熊发现平面上有 $2n$ 个点，满足任意两点不重合、任意三点不共线。现在度度熊要将这 $2n$ 个点划分进两个集合 $A$ 和 $B$ 中，使得 $|A|=|B|=n$，也就是两个集合中的元素个数均为 $n$，并且存在平面上不经过任意一个给定点的直线，使得 $A$ 中的所有点在直线的同侧、$B$ 中的所有点也在直线的同侧，但是 $A$ 中的点和 $B$ 中的点在直线的异侧。

一个划分方案可以用一个长度为 $2n$ 的字符串表示，第 $i$ 个位置是 'A' 表示第 $i$ 个点属于集合 $A$、 是 'B' 则表示第 $i$ 个点属于集合 $B$，两个划分方案不同当且仅当存在一个点在两个方案中属于不同的集合，也就是两个划分方案对应的字符串不同。你需要帮度度熊求出满足条件的划分方案数，并给出一个字典序最小的划分方案。

由于方案数可能很大，同时也是为了 ruin the legend，你只需要输出方案数对 $1000000007(=10^9+7)$ 取模后的值。

记 $|S|$ 为字符串 $S$ 的长度，对于两个字符串 $S$ 和 $T$ ，定义 $S$ 的字典序比 $T$ 小，当且仅当存在非负整数 $k(\leq \min(|S|,|T|))$ 使得 $S$ 的前 $k$ 个字符与 $T$ 的前 $k$ 个字符对应相同，并且要么满足 $|S| = k$ 且 $|T| > k$，要么满足 $k < \min(|S|,|T|)$ 且 $S$ 的第 $k+1$ 个字符比 $T$ 的第 $k+1$ 个字符小。例如 "AA" 的字典序比 "AAA" 小，"AB" 的字典序比 "BA" 小。

请注意，本题时限较紧，你需要尽可能优化算法的实现.

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

接下来依次描述 $T$ 组测试数据。对于每组测试数据：

第一行包含一个整数 $n$，表示要划分出的两个集合的大小。

接下来 $2n$ 行，每行包含两个整数 $x_i, y_i$，表示第 $i$ 个点的坐标。

保证 $ 1 \leq T \leq 10$，$1 \leq n \leq 10^3$，$-10^4 \leq x_i, y_i \leq 10^4$。

对于每组测试数据，输出一行信息 "Case #x: y T"（不含引号），其中 x 表示这是第 $x$ 组测试数据，y 表示满足条件的划分方案数对 $1000000007(=10^9+7)$ 取模后的值，T 表示字典序最小的划分方案，相邻两个字符之间不要有多余空格，行末不要有多余空格。

2
2
0 0
1 1
0 1
1 0
2
0 0
1 1
3 0
0 3

Case #1: 4 ABAB
Case #2: 6 AABB

2018"百度之星"程序设计大赛 - 资格赛