$3s512MB(butterfly.in/out)$

题目描述

花间的蝴蝶一对对，贵客倒没醉我先醉

当你清醒之后，只记得如下问题：

对于一个大小为 $N$ 的序列 $A=(A_1,A_2,...,A_n)$ 和两个整数 $L,R$ 满足 $1\leq L\leq R\leq N$ 和两个整数 $S,T$ 满足 $S\not=T$ 。

定义： $$ F^k(i)=\begin{cases} F^{k-1}(F(i)) \quad \rm if\ (k\not=1)\\ A_i \quad \rm if\ (k=1)\\ \end{cases} $$ 现在有一个 $N$ 个点，$0$ 条边的有向图 $G$ ，按照如下规则给这个图添加边：

• 对于 $1\leq i\leq N,L\leq k\leq R$ ，添加一条 $(i,F^k(i))$ ，长度为 $1$ 的有向边。

并询问从 $S$ 出发能否到达 $T$， 若能的话答案为 $1$ ，否则答案为 $0$ 。

给出质数 $P$ ，对于 $N^N\times \frac{N(N+1)}{2}\times N(N-1)$ 种可能的输入，请输出答案和对 $P$ 取余后的结果。

输入格式

第一行两个整数 $N,P$。

输出格式

一行一个整数表示答案。

样例

样例 1 输入

2 998244353

样例 1 输出

10

样例 2 输入

3 924844033

样例 2 输出

378

样例 3 输入

12 313883611

样例 3 输出

211838194

样例 4

见选手目录下 $\rm butterfly/ex\_butterfly4.in$ 和 $\rm butterfly/ex\_butterfly4.out$。

数据范围

保证对于所有数据满足 $2\leq N\leq 10^5,10^8\leq P\leq 10^9,P$ 为质数。