考慮一個每個格仔入面寫有兩兩唔同數值嘅 $N \times N$ 格仔盤。如下定義兩種操作 $\text{RowShift}(r)$ 同 $\text{ColShift}(c)$：

• $\text{RowShift}(r)$：將第 $r$ 行嘅每個元素向右移一格，最右邊嘅元素移去最左邊。
• $\text{ColShift}(c)$：將第 $c$ 列嘅每個元素向下移一格，最下邊嘅元素移去最上邊。

給定 $(1, 2, \dots, N)$ 嘅一個排列 $(P_1, P_2, \dots, P_N)$，按順序執行以下 $2N$ 個操作稱為一次操作過程：

• 第 $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)$

將操作過程重複足夠多次之後，格仔盤必定會返去初始狀態。請計出最少需要重複幾多次。因為答案可能非常大，請輸出佢對 $998\,244\,353$ 取模嘅結果。

輸入格式

第一行包含一個整數 $N$。（$1 \le N \le 200\,000$）

第二行包含 $N$ 個整數 $P_1, P_2, \dots, P_N$，用空格隔開。$(P_1, P_2, \dots, P_N)$ 係 $(1, 2, \dots, N)$ 嘅一個排列。

輸出格式

輸出操作過程最少需要重複嘅次數對 $998\,244\,353$ 取模嘅結果。

範例

輸入格式 1

2
1 2

輸出格式 1

3

輸入格式 2

3
1 3 2

輸出格式 2

3