405314: GYM101879 K Portuguese Pastimes

Portuguese children's pastimes are very sophisticated. Some of them have very complex rules and their description can get even a grown up dumbfounded, but somehow the kids play with them and have lots of fun. One of them goes by the name of "spin-and-turn". In this game, one of the players writes down an ordering of the participants, and this ordering remains secret. Some other player then tries to guess this ordering with spin-and-turn moves. The idea is to apply several times the same permutation of the participants, starting from the ordering of the children by their ages. If at some point the secret permutation is found, the player wins. Otherwise, the kid who came up with the secret ordering wins.

Let's see an example. Imagine that the secret ordering is $$$(4, 2, 1, 3)$$$, that is, the oldest child comes first, next the second youngest, followed by the youngest child and then the third one. One of the players could play with the permutation $$$(3, 1, 4, 2)$$$. If we apply this permutation from the age ordering $$$(1, 2, 3, 4)$$$ we get $$$(3, 1, 4, 2)$$$. If we do this again on this ordering, we get $$$(4, 3, 2, 1)$$$. And then $$$(2, 4, 1, 3)$$$ and then we get back to the starting ordering $$$(1, 2, 3, 4)$$$. So this player has lost, and the player that chose the secret ordering won. In the game, the kids keep moving, spinning and turning, hence the name$$$\ldots$$$

This very sophisticated game intrigued a famous Portuguese mathematician who decided to study it. Your task in this problem is to help this mathematician. Given a secret ordering $$$p$$$ of the players, we want to find how many permutations $$$q$$$ may result in $$$p$$$ when applied a finite number $$$k \geq 0$$$ of times, as in the example above.

The first line has two integers $$$N$$$ and $$$k$$$, the number of children and the number of times we want to apply a permutation $$$q$$$ to obtain $$$p$$$, respectively. The second line has $$$N$$$ integers separated by a blank space, which gives the ordering represented by permutation $$$p$$$.

Constraints

• $$$1 \leq N \leq 10^5$$$
• $$$0 \leq k \leq 10^6$$$

Print an integer, the number of permutation $$$q$$$ that, when applied $$$k$$$ times, end up with permutation $$$p$$$. Print this answer modulo $$$10^9 + 7$$$.

5 60
1 2 3 4 5

120

5 2
3 5 1 4 2

2