P4223 Expected Inversions

WXH Grand Theorem Law n.

The monastery led by mcfx attempts to summon the legendary “memetic master” WXH through an ancient ritual array. After preparing all the summoning tools, mcfx activates the array to the clatter of many keyboards. Suddenly, heaven and earth darken, and lightning strikes the center of the array. A golden beam descends from the sky, with golden code drifting in midair. Soon, a login interface appears. Upon careful inspection, mcfx sees the following text: "WXHCoder is a problem bank that contains every problem from the past to the future. If you want to log into it, you must solve the following problem." The problem is as follows: You are given a permutation of length $n$. There are $k$ operations. In each operation, two distinct numbers are chosen uniformly at random and swapped. Find the expected number of inversions multiplied by ${{n}\choose{2}}^k$. mcfx discovered that the Constraints are $n, k \le 10^{20010910}$, so he decides to first explore smaller $n, k$. ${n}\choose{2}$ denotes the number of ways to choose two from $n$ balls.

The first line contains two integers $n, k$. The second line contains a permutation of $1$ through $n$.

Output the expected number of inversions multiplied by ${{n}\choose{2}}^k$ modulo $10^9+7$.

$n \le 500000, k \le 10^9$. Translated by ChatGPT 5