# 多类配对的 DNA 双链计数

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

把双链无环 DNA 的计数模型推广到多种互补字母。每次询问可以使用不同的长度、互补对种类数和取模参数。

## 形式化问题描述

一次询问给出 $N,K,P$ .字母表由 $K$ 对不同的字母 $a_1,b_1,\ldots,a_K,b_K$ 组成，共 $2K$ 种。互补关系为 $a_i$ 与 $b_i$ 配对；不同字母对彼此不配对，没有字母与自身配对。

一个含 $N$ 个字母对的双链结构由长度为 $N$ 的字符串 $s$ 表示。反向互补操作为

$$R(s)=\overline{s_N}\,\overline{s_{N-1}}\cdots\overline{s_1}$$

两个字符串表示相同结构，当且仅当它们相等，或者其中一个是另一个的反向互补串。字母种类有固定标记；不同互补对之间不另作重命名等同。

求结构种类数对 $P$ 取模后的非负最小剩余。共有 $M$ 次询问，最终输出全部余数的按位异或。

## 输入格式

第一行整数 $M$ .接下来 $M$ 行，每行三个整数 $N,K,P$ .字母本身不需要输入，配对规则如上定义。

## 输出格式

输出一行一个非负整数，表示每次询问先按各自的 $P$ 取模后，所有结果的按位异或。

## 样例

### 样例 1

### 输入

```text
3
1 1 100
2 1 100
3 2 100
```

### 输出

```text
34
```

### 样例 2

### 输入

```text
4
2 2 2
4 1 4
4 2 1
1 5 7
```

### 输出

```text
7
```

### 样例 3

### 输入

```text
1
2 3 6
```

### 输出

```text
3
```

## 样例解释

第一组的三个计数为 $1,3,32$ ，均小于各自模数，异或为 $34$ .第二组的四个余数为 $0,2,0,5$ ，异或为七。模数为一时，余数总是零。

第三组有六种字母，长度为二，结构种类数为 $21$ ，模六得到三。

![一对互补字母的非固定表示和固定表示](assets/strands.svg)

图中用 `A` 、`T` 表示任意一对互补字母。箭头表示反向互补，左右两图各形成一个等价类。

## 数据范围与保证

对所有数据，$1\le M\le500000$ ，$1\le N,K,P\le10^9$ .$P$ 可以为一、偶数或合数，询问可重复。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |