#P3807. 【模板】卢卡斯定理/Lucas 定理

    ID: 4867 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>递归素数判断,质数,筛法进制组合数学逆元Lucas 定理

【模板】卢卡斯定理/Lucas 定理

题目背景

这是一道模板题。

题目描述

给定整数 n,m,pn, m, p 的值,求出 Cn+mnmodpC_{n + m}^n \bmod p 的值。

输入数据保证 pp 为质数。

注: CC 表示组合数。

输入格式

本题有多组数据

第一行一个整数 TT,表示数据组数。

对于每组数据:

一行,三个整数 n,m,pn, m, p

输出格式

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

2
1 2 5
2 1 5
3
3

提示

对于 100%100\% 的数据,1n,m,p1051 \leq n, m, p \leq 10^51T101 \leq T \leq 10