Note

This problem is derived from F - L to R Graph, but it can be solved independently of Problem F.

Problem Statement

Consider the following problem. The important differences from L to R Graph are shown in red.

You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$ consisting of integers between $1$ and $N$, inclusive, $L,R$ satisfying $1\leq L\leq R\leq N$, and $S,T$ satisfying $1\leq S\leq N,1\leq T\leq N,S\ne T$.

Let $F(i)=A_i$. Also, let $F^k(i)$ denote the result of composing $F(i)$ $k$ times.

There is a directed graph with $N$ vertices and $0$ edges, whose vertices are numbered from $1$ to $N$. Perform the following operation on this graph.

• For $1 \leq i \leq N,L \leq k \leq R$, add an edge from vertex $i$ to vertex $F^k(i)$.

Determine whether vertex $T$ is reachable from vertex $S$.

You are given $N$ and a prime $P$. There are $N^N\times \frac{N(N+1)}{2}\times N(N-1)$ possible inputs to the above problem. Among them, find the number of inputs in which vertex $T$ is reachable from vertex $S$, modulo $P$.

Input

$N\ P$

• $2\leq N\leq 10^5$
• $10^8\leq P\leq 10^9$
• $P$ is prime.
• All inputs are integers.

Output

Output the answer on $1$ line.

Sample

2 998244353

10

3 924844033

378

12 313883611

211838194