アリスは$k$個の貴重な記憶を持っており，それぞれにはそれが起こった時系列順に対応する$1$から$k$までのユニークな幸福度が割り当てられている．彼女は自分の過去を探求するために，$n$個の魔法の呪文の列を刻み込んだ．$i$番目の呪文は，置換$A_i$に従って彼女の記憶を並べ替える．連続する呪文の列が唱えられると，それらの効果が合成され，心の中に新しく複雑な並べ替えが生じる．

呪文が記憶のタイムラインをシャッフルするにつれて，後の記憶（幸福度が高いもの）が前の記憶の前に置かれてしまうことがある．この時間的な不協和によって，アリスはそれを後悔のペアと呼ぶ——自然な時系列の幸福度の順序が逆転している瞬間である．好奇心に駆られた彼女は，すべての可能な連続する呪文の区間に対して生じる後悔のペアの総数を数えることで，感情的な不協和の総量を測定したいと考えている．

形式的には，$k$個の記憶と$n$個の置換の列が与えられ，$i$番目の置換を$A_i$とする．各$A_i$は$\{1, 2, \ldots, k\}$の置換である．任意の2つの置換$p$と$q$に対して，その合成$p \circ q$は次のように定義される： $$(p\circ q)(x)=p(q(x)).$$

呪文の任意の連続区間$[l, r]$（ただし$1 \le l \le r \le n$）に対して，$P_{l,r}$を呪文が合成された後の最終的な置換とする．これは次のように定義される：（置換の合成の結合性により，この積の括弧の付け方は重要ではない．例えば，$(A_l\circ A_{l+1})\circ A_{l+2}=A_l\circ(A_{l+1}\circ A_{l+2})$である．置換の順序は書かれた通りに固定されている．） $$P_{l,r}=A_l\circ A_{l+1}\circ\cdots\circ A_r.$$

あなたの仕事は，すべての連続する呪文の区間における後悔のペアの総数を計算することである．形式的には，次の値を計算せよ： $$\sum_{1\le l\le r\le n}\operatorname{inv}(P_{l,r}),$$ ここで$\operatorname{inv}(p)$は置換$p$における転倒数を表し，$1\leq xp(y)$となる組$(x,y)$の数と定義される．

入力

最初の行には2つの整数$n$と$k$が含まれる（$1\le n,k\le 10^5$，$nk\le 10^5$）．

続く$n$行のそれぞれには$k$個の整数が含まれる．$i$行目には置換$A_i(1),A_i(2),\ldots,A_i(k)$が与えられる．

出力

答えを表す1つの整数を1行に出力せよ．

入出力例

入力例 1

2 3
1 3 2
2 3 1

出力例 1

6

入力例 2

6 5
5 3 1 4 2
2 4 3 1 5
5 4 2 3 1
1 3 4 5 2
2 5 3 4 1
1 2 5 4 3

出力例 2

116

注記

最初のテストケースについて：

• $A_1=[1,3,2]$と$A_2=[2,3,1]$の転倒数はそれぞれ$1$と$2$である．
• それらの合成は$A_1\circ A_2=[3,2,1]$であり，その転倒数は$3$である．
• 空でない3つの連続区間について合計すると$1+2+3=6$となる．

2番目のテストケースでは，連続区間は全部で$21$個ある．区間の長さごとにグループ化すると，転倒数の和は次のようになる： [ 32,\ 28,\ 24,\ 12,\ 12,\ 8. ] それらの合計は$116$である．