#P18354. Not a work of Idol

Not a work of Idol

Not a work of Idol

输入:标准输入
输出:标准输出

题目描述

一个简单无向图称为 dd-正则图,当且仅当图中的每个顶点度数都恰好为 dd。

给定 n,dn,d 和一个素数 pp,求顶点集合为 {1,2,…,n}\{1,2,\ldots,n\} 的简单无向 dd-正则图数量,答案对 pp 取模。

顶点有标号。只要两张图的边集不同,就视为不同的图。图不允许自环或重边,不要求连通。

输入格式

第一行包含两个整数 T,pT,p,分别表示询问数量和取模所用的素数。同一输入文件的所有询问共用这个 pp。

接下来 TT 行,每行包含两个整数 n,dn,d,表示一次询问。

输出格式

对于每个询问,输出一行一个整数,表示有标号简单无向 dd-正则图数量对 pp 取模的结果。

数据范围

  • 1≤T≤1041\le T\le10^4;
  • p∈{2,3,5,7}p\in\{2,3,5,7\};
  • 0≤d<n≤10180\le d<n\le10^{18}。

样例输入 1

5 3
3 2
9 6
20 10
100 10
1919810 114514

样例输出 1

1
1
2
0
0