まず，順列 \(p\) と最終的に表になっているコインの枚数 \(k\) を対応付けましょう．

\(i \rightarrow p_i \rightarrow p_{p_i} \rightarrow \cdots\) という形の列を考えます． ここで，\(i < p_i < p_{p_i} < \cdots\) となる（つまり単調増加になる）極大な列を “chain” と呼ぶことにします．

順列 \(p\) のサイクルを極大な chain の集合に分解したとします． このとき，操作の様子から，奇数長の chain の個数が\(k\)に一致することがわかります．

奇数個の chain が \(k\) 個であるような順列 \(p\) の個数を直接数えるのは難しいです． そこで，答えが同じになる別の問題を考え，そちらを解くことにします．

順列 \(p\) に対して，別の順列 \(q\) を対応させる次のような写像 \(f(p)=q\) を考えます．

• まず \(p\) のサイクル分解を考える．
• \(i\) 個目のサイクルを \(x_{i,1} \rightarrow x_{i,2} \rightarrow \cdots \rightarrow x_{i,1}\) とおく．この時，\(x_{i,1}\) がこのサイクルに登場する index の中で最小になるようにする．
• さらに，サイクル同士の順番を，\(x_{1,1}>x_{2,1}>\cdots\) となるようにする．
• \(x_1,x_2,\cdots\) をこの順番に並べると \(\{1,2,\cdots,N\}\) の順列が得られるので，これを \(f(p)\) とする．

ここでまず，\(f\) には逆写像が存在することが言えます． つまり，順列 \(q\) が与えられたとき，\(f(p)=q\) を満たす順列 \(p\) が一意に定まります． これは，\(q\) を前から見てゆき，prefix-min が更新されるタイミングで新しいサイクルを作るようにしていけばよいです．

\(q\) の単調増加な連続部分列のうち，極大なものを “run” と呼ぶことにします． この時，\(p\) の chain が \(q\) の run に対応することがわかります．

よって，以下の問題が解ければよいことになります．

• 順列 \(q\) を考える．奇数長の run がちょうど \(k\) 個あるとき，\(W^k\) のスコアがもらえる．\(q\) を全通り試したときのスコアの総和はいくつか？

各 run について，その要素を先頭から 2 個ずつペアにしていくことにします．ペアにした 2 要素には順に A,B，余ったものに C というラベルをつけてみます． 奇数長の run の個数は C の個数になります． この時，最終的にできる ABC 列は，以下のような形になります．

• (C が \(0\) 個以上 \(+\) AB) が \(0\) 個以上 \(+\) (C が \(0\) 個以上)

ここで，このような ABC 列を一つ固定して，その列に対応する順列を数えてみます． まず， (C が \(0\) 個以上 \(+\) AB) というブロックごとに，その内部の相対順序を考える必要があります． そして逆にそれさえ満たしていれば対応する順列が作れます． つまり，ブロックを跨ぐような制約は考える必要がありません． （(C が \(0\) 個以上) のブロックも同様です）

ありうる ABC 列すべてにわたってこれらの数え上げを行うためには，DP をすればよいです．\(dp[i]=\)長さ \(i\) の順列の重みの総和，として，\(dp[i] \to dp[j]\) の遷移は，(C が \((j-i-2)\) 個 \(+\) AB) というブロックを足すことにすればよいです． この DP を愚直に行えば \(O(N^2)\) ですが，これは分割統治とFFT で高速化でき，\(O(N\log^2N)\) 時間のアルゴリズムが得られます．

なお，形式的冪級数の inverse を考えることにより，\(O(N\log N)\) 時間でも解くことができます．