操作全体を通して生成される \(2N\) 個の実数を，その大小関係を保ったまま \((1,2,\cdots,2N)\) の順列に対応させます． すると，すべての順列が等確率で現れます．これで問題を離散的な設定で考えられるようになりました．

\(i=1,2,\cdots,2N\) に対して，\(i\) を区間の右端として使うか左端として使うかを順に決めていくことにします． ある \(i\) を区間の右端として使うと決めたとき，それと対応する左端として選ぶ位置には自由度があります． 右端の個数はちょうど \(N\) 個であり，それぞれについて対応する左端の候補の個数を\(x_1,x_2,\cdots,x_N\) と書くことにします．

まず，それぞれの \(i\) について右端として使うか左端として使うかを決めると \(x\) が定まります．また，シールが \(K+1\) 枚以上重ならないという条件は，\(x\) のすべての要素が \(K\) 以下であることを意味します． また，左端の候補の個数が変化する様子を考えると，\(x_{i+1} \geq x_i-1\) が \(x\) の必要条件になります． 更に，\(x_N=1\) も必要です．

逆に，これらの必要条件をすべて満たす \(x\) を取ると，それに対応するように各 \(i\) が右端か左端かどうかが一意に定まります．

よって，結局次の問題が解ければ良いことになります．

• 以下の条件を満たす整数列 \(x_1,x_2,\cdots,x_N\) すべてについて \(\prod_{1 \leq i \leq N} x_i\) を計算した際の和はいくらになるか．
  • \(1 \leq x_i \leq K\)
  • \(x_{i+1} \geq x_i-1\)
  • \(x_N=1\)

\(2\) 番目の条件に注目して，これに対して包除原理を用いて数え上げを行います． この条件を満たさない \(i\) を任意に固定したとします． そのような \(i\) が連続する部分に注目すると，数列をいくつかの”ブロック”に分解することができます． 各ブロック内の値の決め方の総数は，以下のようにして求まります．

• 長さ \(m\) (\(1 \leq m \leq N\)) の数列 \(K \geq y_1 > y_2 > \cdots > y_m \geq 1\) であって，\(y_j-2 \geq y_{j+1}\) (\(1 \leq j \leq m-1\)) を満たすものすべてについて，\(\prod_{1 \leq i \leq m} y_i\) を計算した際の和．

これは分割統治 & FFT で求めることができます． 具体的には，\(y\) の値域が \(l\) 以上 \(r\) 以下であるときの答えを求める関数を用意し，これを再帰的に呼べばよいです． ただしここで関数の戻り値は，\(l\) 及び \(r\) を使っているかどうかで分類した \(2 \times 2\) 個の値を返す必要があります．

これで各ブロック内の値の決め方が分かるため，あとはこれを使って DP をすればよいです． この DP は，分割統治 & FFT，もしくは多項式の inv を求めることで高速に計算できます． 最後のブロックだけは必ず \(1\) を使う必要があることに注意してください．

計算量は \(O(N \log^2N + K \log^2K)\) もしくは \(O(N \log N + K \log^2K)\) になります．

解答例(c++)

なお，実は \(O(N \log N)\) で解くこともできます． \(N=0,1,2,\cdots,\lceil K/2 \rceil\) における元の問題の答えは \(1,1,3,15,105\cdots\) だと簡単にわかります． また，この数列の母関数の分母を考えると，これは，\(N\) 頂点から \(K\) 個のマッチングを取る方法の総数と一致することがわかります．これは帰納法によって証明できます．（ちなみに OEIS にも存在します．） よってこれらの情報から，\(K\)を固定した際の \(N\) ごとの答えを並べた数列を復元できます． （この解法は tourist さんの提出を参考にしています．）

解答例(c++)