Betrachte ein $N \times N$-Gitter, dessen Zellen paarweise verschiedene Werte enthalten. Wir definieren zwei Operationen, $\text{RowShift}(r)$ und $\text{ColShift}(c)$, wie folgt:

• $\text{RowShift}(r)$: Verschiebe jedes Element in Zeile $r$ um eine Zelle nach rechts, wobei das am weitesten rechts stehende Element in die am weitesten links stehende Zelle wandert.
• $\text{ColShift}(c)$: Verschiebe jedes Element in Spalte $c$ um eine Zelle nach unten, wobei das unterste Element in die oberste Zelle wandert.

Gegeben sei eine Permutation $(P_1, P_2, \dots, P_N)$ von $(1, 2, \dots, N)$. Das nacheinander Ausführen der folgenden $2N$ Operationen in dieser Reihenfolge wird als ein Vorgang bezeichnet:

• $1$.: $\text{RowShift}(1)$
• $2$.: $\text{ColShift}(P_1)$
• $3$.: $\text{RowShift}(2)$
• $4$.: $\text{ColShift}(P_2)$
• $\vdots$
• $2N - 1$.: $\text{RowShift}(N)$
• $2N$.: $\text{ColShift}(P_N)$

Wenn man den Vorgang hinreichend oft wiederholt, kehrt das Gitter garantiert in seinen Ausgangszustand zurück. Bestimme die minimale Anzahl erforderlicher Wiederholungen. Da die Antwort sehr groß sein kann, gib sie modulo $998\,244\,353$ aus.

Eingabe

Die erste Zeile enthält eine ganze Zahl $N$. ($1 \le N \le 200\,000$)

Die zweite Zeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen $P_1, P_2, \dots, P_N$. $(P_1, P_2, \dots, P_N)$ ist eine Permutation von $(1, 2, \dots, N)$.

Ausgabe

Gib die minimale Anzahl der Wiederholungen des Vorgangs modulo $998\,244\,353$ aus.

Beispiele

Eingabe 1

2
1 2

Ausgabe 1

3

Eingabe 2

3
1 3 2

Ausgabe 2

3