【模板】卢卡斯定理

题目背景

这是一道模板题。

题目描述

给定整数 $n, m, p$ 的值,求出 $C_{n + m}^n \bmod p$ 的值。 输入数据保证 $p$ 为质数。 注: $C$ 表示组合数。

输入输出格式

输入格式


**本题有多组数据**。 第一行一个整数 $T$,表示数据组数。 对于每组数据: 一行,三个整数 $n, m, p$。

输出格式


对于每组数据,输出一行,一个整数,表示所求的值。

输入输出样例

输入样例 #1

2
1 2 5
2 1 5

输出样例 #1

3
3

说明

对于 $100\%$ 的数据,$1 \leq n, m, p \leq 10^5$,$1 \leq T \leq 10$。