问题 4826 --3.合影队形

4826: 3.合影队形

题目描述

  有 $n$ 个神仙在操场上排成一排合影。
但是对于每个神仙,他一定没有或者只有一个自己最敬仰的巨佬,他希望站在自己最敬仰的巨佬的左边,但不一定要相邻。
请问在满足神仙们的要求的前提下,有多少种不同的排队方式。
两种方案不同当且仅存在至少一个神仙,他在这两个方案当中站的位置不同。

输入

本题的每个测试点包含多组数据。
第一行包含一个整数 $T$ ,表示数据组数。
对于每一组数据,第一行三个整数 $n,m,p$,分别表示志愿者数、这样的要求的个数和模数,保证 $p$ 为质数。
接下来 $m$ 行,每行两个整数$x,y$ ,表示 $x$ 必须在$y$  左边。

输出

输出总共 $T$  行,每行一个整数。
第 $i$ 行的数表示第 $i$  组数据的答案对该组数据的 $p$ 取模的结果。

样例输入输出

输入#1 复制
2
3 1 17
1 2
5 0 101
输出#1 复制
3
19
输入#2 复制
1
10 8 91
2 8
9 8
7 6
5 6
3 4
1 6
4 9
10 2
输出#2 复制
42

提示

样例解释 1
对于第一组询问,总共三种方案:123,132,312。
对于第二组询问:由于没有限制,所以总共有 $5!=120$ 种不同的方案,模 101 后是 19 。
对于 $15\%$  的数据,$ n,m \leq 9$ ;
对于 $30\%$  的数据,$ n,m \leq 17$ ;
对于 $50\%$  的数据,$ n,m \leq 20$ ;
对于 $70\%$  的数据,$ n,m \leq 2000$ ;
对于 $100\%$  的数据, $0\leq m \leq n \leq 2 \times 10^5, n+10 \leq p \leq 10^9+7, T \leq 10$。

序号 标题 作者 发表时间 费用 订购数 操作