【模板】卢卡斯定理(Lucas Theorem)

题目描述

这是一道模板题。

给定整数 $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$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接