よい数列は，右に \(N\) 回，上に \(M\) 回進む経路として解釈できます．そこで，これからは R,U がそれぞれ \(N,M\) 個ある文字列に対して重みを計算してみます．

まず \(K=N\) のときの解き方を考えます．

各 R について，それより左の U を一つ選んで”親”とする (\(a_i\) に対応) か，もしくは印をつける (\(x\) に対応) という \(2\) 択を選ぶことができる，という設定だと解釈できます．

印が \(i\) 個あるような方法が何通りあるかを数えてみます． 各 U について，それに付随する R が何個あるかを決めると，その並べ方は二項係数で決まります． 結局求めたいのは，\([x^{N-i}](\frac{\exp(x)-1}{x})^M\) です．

よって，\(K=N\) なら単に \((\frac{\exp(x)-1}{x})^M\) を求めてやるだけで良いです．

\(K<N\) について考えます． \(a_{K+1}\) の値ごとに分類して数えることにします． \(h=a_{K+1}\) を固定してみます． まず，\(\prod_{1 \leq i \leq K} (a_i+x)\) の部分に関しては先程と全く同じように計算できて，\((\frac{\exp(x)-1}{x})^h\) を計算すればよいです． では \(\prod_{K+1 \leq i \leq N} a_i\) の部分がどうなるかというと，これも先ほどと同様に問題を変形して，\(h \times [x^{N-1-K}] (\frac{\exp(x)-1}{x})^{M-h} \exp(x)^h = h \times [x^{N-1-K}] (\frac{\exp(x)-1}{x})^{M} (\frac{x \exp(x)}{exp(x)-1})^h\) の計算に帰着されます．

よって，各\(h\) について，後半部分の重みを power projection で求めたあと，それを前半部分の式に組み合わせ，これを composition で計算すれば答えが求まります．

計算量は \(O(N\log^2N + M \log M)\) です．

回答例(C++)