No testdata at current.

题意翻译

有这样一个问题：给出一个长为 nn 的排列 pp，并且给出长为 nn 的排列 QQ。依次建立无向边 (i,Pi,Qi)(i,Pi​**,Qi​)，其中 QiQi​** 是边权。

现在可以删除一些边，求使得原图不存在环所需删除的边的最小权值和。

Alice 的解决方案是：依次枚举边 1,2…n1,2…n，若该边当前情况下在一个环中，将其删掉，并累加答案。

Bob 的解决方案是：依次枚举边 n,n−1…1n,n−1…1，若该边当前情况下在一个环中，将其删掉，并累加答案。

求对于 (n!)2**(n!)2 个不同的 P,QP**,Q 组合，能使得 Alice 和 Bob 都给出错误的答案的排列个数，对 998244353998244353 取模。

1≤n≤2×1051≤n≤2×105

题目描述

すぬけくんは以下の問題を考えました。

(1,2,…,N)(1,2,…,N) の順列 P=(P1,P2,…,PN),Q=(Q1,Q2,…,QN)P=(P1​**,P2​,…,PN​),Q=(Q1​,Q2​,…,QN​)** が与えられます。 以下の方法で NN 頂点 NN 辺のグラフを作ります。

• i=1,2,…,Ni=1,2,…,N の順に、頂点 ii と頂点 PiPi​ を双方向に結ぶ重さ QiQi​ の辺を張る。

グラフが閉路を含まないように何本か辺を削除するとき、削除する辺の重みの総和の最小値を求めてください。

Alice と Bob は以下の解法をそれぞれ考えました。

Alice： 答えを 00 で初期化する。i=1,2,…,Ni=1,2,…,N の順に、頂点 ii と頂点 PiPi​ を結ぶ辺が閉路に含まれるならその辺を削除し、削除した辺の重みを答えに加算する。

Bob： 答えを 00 で初期化する。i=N,N−1,…,1i=N,N−1,…,1 の順に、頂点 ii と頂点 PiPi​ を結ぶ辺が閉路に含まれるならその辺を削除し、削除した辺の重みを答えに加算する。

すぬけくんは Alice と Bob の解法がどちらも誤っていることに気付いたので、二人の解法の答えが共に正しい答えと異なるような入力の個数が知りたくなりました。

入力は (N!)2**(N!)2 通り考えられますが、その内 Alice と Bob の解法の答えが共に正しい答えと異なるものの個数を 998244353998244353** で割ったあまりを求めてください。

输入输出格式

输入格式

入力は以下の形式で標準入力から与えられる。

NN

输出格式

答えを整数として出力せよ。

输入输出样例

输入样例 #1

3

Copy

输出样例 #1

4

Copy

输入样例 #2

2

Copy

输出样例 #2

0

Copy

输入样例 #3

6

Copy

输出样例 #3

314708

Copy

输入样例 #4

318

Copy

输出样例 #4

321484323

Copy

说明

制約

• 1≤N≤2×1051≤** N≤** 2×** 10**5
• 入力される数値は全て整数