UOJ Logo Universal Online Judge

UOJ

#961. 【UR #30】赛场设计

附件下载 统计

English Problem Statement

伏特正在设计马拉松赛场的道路,以确保物资运输和观众流动的秩序。

伏特选定了 n 个站点,他可以在 n 个站点之间铺设若干单向道路,不能铺设重复的道路。

伏特不希望跳蚤们迷路:铺设的道路不能有环。

伏特希望赛场道路有良好的交通:不能存在三个站点 (a,b,c),使得 a 不能到达 bb 不能到达 cc 不能到达 a

称满足上述两条限制的道路铺设方案为好图。伏特想知道好图有多少种,这个数字可能很大,你需要求出答案在模素数 P 意义下的值。

输入格式

一行两个整数,分别表示 nP

输出格式

一行一个整数,表示答案对 P 取模的值。

样例一

input

3 835199921

output

18

explanation

下记 (x,y) 表示 xy 的单向道路。

选择边集 (1,2),(1,3) 是好图,通过交换点的标号可以获得 3 种好图。

选择边集 (1,2),(2,3) 是好图,通过交换点的标号可以获得 6 种好图。

选择边集 (1,2),(1,3),(2,3) 是好图,通过交换点的标号可以获得 6 种好图。

选择边集 (1,3),(2,3) 是好图,通过交换点的标号可以获得 3 种好图。

选择边集 (1,2) 不是好图,因为存在:1 无法到 33 无法到 22 无法到 1

选择边集 (1,2),(2,1) 不是好图,因为存在环 (1,2),(2,1),不属于 DAG。

一共有 3+6+6+3=18 种三个点的好图。

样例二

input

16 828234769

output

372590002

样例三~九

见附件下载。

对于所有样例,保证第 i 个样例满足第 i 个子任务的约束。

数据范围

对于所有数据,保证 1n106108P109P 是素数。

子任务编号 分值 n 特殊性质
1 12 5
2 12 18
3 8 200
4 10 5000 P=998244353
5 10 5000
6 12 2×105 P=998244353
7 12 2×105
8 12 106 P=998244353
9 12 106

时间限制:1s

空间限制:512MB