C. Shift And Think
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Professor Hussein is a renowned researcher in digital signal processing. He models complex, repeating signals as permutations. A permutation of length $$$n$$$ is an arrangement of the integers from $$$1$$$ to $$$n$$$, inclusive, where each integer appears exactly once.

For example, $$$[2, 1, 4, 3]$$$ and $$$[1, 2]$$$ are permutations, while $$$[1, 3, 1]$$$ and $$$[1, 2, 4]$$$ are not.

A key operation in the professor's analysis is the cyclical left rotation. Given a permutation $$$p$$$, we define $$$\mathrm{rot}(p)$$$ as the permutation obtained by shifting $$$p$$$ one position to the left, with the first element wrapping around to the end.

For example, if $$$p = [1, 3, 4, 2]$$$, then $$$\mathrm{rot}(p) = [3, 4, 2, 1]$$$.

More generally, $$$\mathrm{rot}^i(p)$$$ is the result of applying the left rotation operation $$$i$$$ times. For instance, $$$\mathrm{rot}^2(p) = [4, 2, 1, 3]$$$.

Professor Hussein is particularly interested in a property he calls stable indices. An index $$$i$$$ (where $$$1 \le i \le n$$$) is a stable index of a permutation $$$p$$$ if applying the permutation mapping twice, starting from that index, returns the original index. Formally, $$$i$$$ is a stable index if: $$$$$$p[p[i]] = i$$$$$$

We denote $$$S(p)$$$ as the total number of stable indices in the permutation $$$p$$$.

Example:

Let $$$p = [3, 6, 1, 4, 2, 5]$$$.

  • Index 1: $$$p[1] = 3$$$. $$$p[p[1]] = p[3] = 1$$$. Since $$$p[p[1]] = 1$$$, index 1 is stable.
  • Index 2: $$$p[2] = 6$$$. $$$p[p[2]] = p[6] = 5$$$. Since $$$5 \neq 2$$$, index 2 is not stable.
  • Index 3: $$$p[3] = 1$$$. $$$p[p[3]] = p[1] = 3$$$. Since $$$p[p[3]] = 3$$$, index 3 is stable.
  • Index 4: $$$p[4] = 4$$$. $$$p[p[4]] = p[4] = 4$$$. Since $$$p[p[4]] = 4$$$, index 4 is stable.
  • Indices 5 and 6 are not stable.

Thus, $$$S(p) = 3$$$.

Given a permutation $$$p$$$ of length $$$n$$$ and a total number of rotations $$$k$$$, you must calculate the sum of the stable index counts for the first $$$k$$$ rotations (starting from the 0-th rotation, which is $$$p$$$ itself).

Your goal is to compute: $$$$$$\sum_{i=0}^{k-1} S(\mathrm{rot}^i(p))$$$$$$

Since $$$k$$$ can be extremely large, a simple simulation of each rotation is not feasible.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — the length of the permutation and the total number of rotations to sum over.

The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$), representing the elements of the initial permutation $$$p$$$.

Output

Print a single integer representing the calculated Total Stability Score.

Examples
Input
6 3
3 6 1 4 2 5
Output
6
Input
4 5
1 2 3 4
Output
12