First, let us correlate the permutation \(p\) and the final number of coins \(k\) that face up.

Consider a sequence of the form \(i \rightarrow p_i \rightarrow p_{p_i} \rightarrow \cdots\) Let chain be a maximal such sequence such that \(i < p_i < p_{p_i} < \cdots\) (that is, increasing).

Assume that the cycles in the permutation \(p\) are decomposed into sets of chains. Then, considering how the operations are done, it can be seen that the number of odd length chains equals \(k\).

It is difficult to directly count the permutations \(p\) with \(k\) odd length chains, so we will consider a different problem with the same answer and solve it.

Consider a mapping \(f(p)=q\) that assign to a permutation \(p\) another permutation \(q\).

• First, consider the decomposition of \(p\) into cycles.
• Let \(x_{i,1} \rightarrow x_{i,2} \rightarrow \cdots \rightarrow x_{i,1}\) be the \(i\)-th cycle. Here, make \(x_{i,1}\) the smallest index that appears in this cycle.
• Additionally, order the cycles so that \(x_{1,1}>x_{2,1}>\cdots\)
• Arranging \(x_1,x_2,\cdots\) in this order yields a permutation of \(\{1,2,\cdots,N\}\), which we define to be \(f(p)\).

Here, it can be first seen that \(f\) has an inverse mapping. That is, for a given permutation \(p\), there uniquely exists \(p\) such that \(f(p)=q\). This can be obtained by scanning the elements of \(q\) from the front and making a new cycle when the prefix minimum is updated.

Let run be a maximal increasing contiguous subsequence of \(q\). Then, it can be seen that a chain in \(p\) corresponds to a run in \(q\).

Therefore, we have the following problem.

• Consider a permutation \(q\). When \(q\) has exactly \(k\) odd length runs, we get a score of \(W^k\). What is the sum of the scores for all possible \(q\)?

For each run, let us group the elements into pairs from the front. Label the elements in each pair A, B in this order, and the leftover element C. The number of odd length runs is equal to the number of C. Here, the final sequence of ABC has the following form:

• zero or more (zero or more C \(+\) AB) \(+\) (zero or more C)

Now, let us fix one such ABC sequence and try to count permutations corresponding to that sequence. First, for each block of (zero or more C \(+\) AB), the relative order of the elements inside must be considered. On the other hand, it is the only requirement when making the corresponding permutations. That is, there is no need to consider constraints that straddle multiple blocks. (The same goes for the block of (zero or more C).)

We can use DP to count these for all possible ABC sequences. Let \(dp[i]=\) the sum of weights of all permutations of length \(i\). In the transition \(dp[i] \to dp[j]\), the block of (\((j-i-2)\) Cs \(+\) AB) should be added. If implemented naively, this DP takes \(O(N^2)\) time, but we can optimize it by divide-and-conquer FFT to yield an \(O(N\log^2N)\) algorithm.

The problem can also be solved in \(O(N\log N)\) time by considering the inverse of a formal power series.