問題文

ある$n$に対する$[1,2,\ldots,n]$の置換(permutation) $x$に対し、$f(x)$を辞書順で$x$の次の置換とする。 ただし、$x$が辞書順で最後のもの$[n,n-1, \ldots, 1]$である場合は、$f(x)$を辞書順で最初のもの$[1,2,\ldots,n]$として定義する。 たとえば、$f([1, 2, 3]) = [1, 3, 2]$, $f(f([3,1,2])) = f([3,2,1]) = [1,2,3]$ となる。

置換$x$の転倒数(inversion number)を${\rm inv}(x)$と表す。 たとえば、${\rm inv}([2,1,3]) = 1, {\rm inv}([3,2,1]) = 3$である。

置換$p$が与えられたとき、置換の列$A$を、$A_0 = p$, $A_i = f(A_{i-1})$ ($i \in [1,2,\ldots]$) として定義する。 つまり、$A_i$は$p$に$f$を$i$回適用したものである。 たとえば、$p = [2,1,3]$ なら $A = [[2,1,3],[2,3,1],[3,1,2],[3,2,1],[1,2,3],\dots]$ となる。 $A$の添字は0から始まることに注意せよ。

整数$N$, 整数$K$, 長さ$N$の置換$p$が入力として与えられる。$\displaystyle \sum_{i=0}^{K-1} {\rm inv}(A_i)$を$1000000007$で割った余りを求めよ。

入力

$N$ $K$
$p_1$ $p_2$ $\ldots$ $p_N$

1行目に、整数$N (1 \le N \le 10^5)$, 整数$K (0 \le K \le 10^{18})$が空白区切りで与えられる。 2行目に、長さ$N$の$[1,2,\ldots,N]$の置換$p (1 \le p_i \le N)$が空白区切りで与えられる。

出力

$\displaystyle \sum_{i=0}^{K-1} {\rm inv}(A_i)$を$1000000007$で割った余りを1行に出力せよ。

サンプル

3 5
2 1 3

8

3 36
1 2 3

54

1 1000000000000000000
1

0

2 1000000000000000000
1 2

500000028