交通管控

Problem Description

H 市市中心一共有 $k$ 个路口，今天市中心的交通十分拥堵，因此需要通过交管中心进行手动控制灯的调整来使得不同的路口分别显示红黄绿三种颜色的灯。 由于操作杆使用的频率过高，今天有些操作杆不好使了，交管中心只能使用 $n$ 个可以同时调控 $k$ 个路口的灯的操作杆。对于一个操作杆，其只有 使用 和 不使用 两种状态。若使用该操作杆，每个路口信号灯的变化规律以一个长度为 $k$ 的仅包含 $\texttt{+}$，$\texttt{-}$，$\texttt{0}$ 的字符串组成，若第 $i$ 位为 $\texttt{+}$，则第 $i$ 个路口的信号灯变化规律为：红变为绿，绿变为黄，黄变为红；若第 $i$ 位为 $\texttt{-}$，则第 $i$ 个路口的信号灯变化规律为：绿变为红，黄变为绿，红变为黄；若第 $i$ 位为 $\texttt{0}$，则该操作杆对第 $i$ 个路口的信号灯无操作。 但他们很快发现，如果只通过这几个操作杆来进行操作的话，会有一些信号灯组合表示不出来，于是他们想知道如果初始每个路口信号灯为绿灯，在操作完操作杆后能表示出的不同的信号灯组合以及实现这种排列的操作杆使用方法数。由于这个方案数可能很大，请对给定的一个模数 $M$ 取模。

Input

第一行一个整数 $T$（$1\le T\le 100$），表示测试数据组数。 对于每组数据，第一行三个整数 $n,k,M$（$1\le n\le 500,1\le k\le 10,2\le M\le 10^9+7$），分别表示操作杆数，红绿灯数目和给定的模数。 接下来 $n$ 行，第 $i$ 行有一个长为 $k$ 的字符串。字符串中仅包含 $\texttt{+}$，$\texttt{-}$ 和 $\texttt{0}$ 三种字符。 保证对于所有数据，$n$ 之和不超过 $2\times 10^3$。

Output

对于每组数据，令 $\texttt{A}$ 表示绿灯，$\texttt{B}$ 表示黄灯，$\texttt{C}$ 表示红灯，按字典顺序先输出能表示的红绿信号灯组合，再输出实现这种排列的操作杆使用方法数，对这组数据给定的模数 $M$ 取模。

Sample Input

2
2 3 114514
+-0
+++
3 2 2
-0
00
00

Sample Output

AAA 1
BBB 1
BCA 1
CAB 1
AA 0
CA 0

Source

2024“钉耙编程”中国大学生算法设计超级联赛（6）