题目描述

杨辉三角（又称帕斯卡三角）是一个数字三角形，其数字按交错行排列，满足以下性质：

$a_{n,0} = 1$ （$n \geq 0$）
$a_{n,n} = 1$ （$n \geq 0$）
$a_{n,r} = a_{n-1,r-1} + a_{n-1,r}$ （$0 < r < n$）

考虑一个十进制数$p$，它由杨辉三角第$n$行的数字按顺序拼接而成，其中每个数字用$k$位十进制表示（不足$k$位时补前导零），且满足对于所有$0 \leq r \leq n$，$\log_{10}a_{n,r} < k$。以下是一些示例：

由于$p$的数值可能非常大，你的任务是计算$p \mod m$，其中$m$为给定的整数。

输入格式

输入包含$T$个测试用例。第一行为测试用例数量$T$。每个测试用例占一行，包含三个整数$n$、$k$、$m$（$0 \leq n \leq 1\,000\,000$，$1 \leq k \leq 1\,000\,000$，$2 \leq m \leq 10^9$）。

输出格式

对于每个测试用例，输出$p \mod m$，每个结果占一行。

输入样例 1

3
0 2 7
2 2 12345
5 2 1000000

输出样例 1

1
10201 
100501

提示

由于输入规模较大，建议使用更快的输入输出方法。

题目来源

POJ Monthly--2006.09.29, Kim, Chan Min (kcm1700@POJ)