注意

この問題は F - L to R Graph から派生した問題ですが、F問題とは独立に解くことが可能です。

問題文

以下のような問題を考えます。ただし、L to R Graphとの重要な相違点を赤字で示しています。

$1$ 以上 $N$ 以下の整数からなる長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ 、$1\leq L\leq R\leq N$ を満たす $L,R$ 、$1\leq S\leq N,1\leq T\leq N,S\ne T$ を満たす $S,T$ が与えられます。

$F(i)=A_i$ とします。また、$F(i)$ を $k$ 回合成したものを $F^k(i)$ とします。

頂点に $1$ から $N$ までの番号が付いた $N$ 頂点 $0$ 辺の有向グラフがあります。このグラフに以下の操作を行います。

• $1 \leq i \leq N,L \leq k \leq R$ について頂点 $i$ から頂点 $F^k(i)$ への辺を張る。

頂点 $S$ から頂点 $T$ に到達できるか判定してください。

$N$ と素数 $P$ が与えられます。入力としてあり得るものは $N^N\times \frac{N(N+1)}{2}\times N(N-1)$ 通りありますが、そのうち、頂点 $S$ から頂点 $T$ に到達できる入力の個数を $P$ で割った余りを求めてください。

入力

$N\ P$

• $2\leq N\leq 10^5$
• $10^8\leq P\leq 10^9$
• $P$ は素数
• 入力はすべて整数

出力

$1$ 行に、答えを出力してください。

サンプル

2 998244353

10

3 924844033

378

12 313883611

211838194