問題を次のように言い換えます．

\(N\) 個の石を用意し，黒と白に塗ることを考えます． 石 \(i\) を黒く塗るときは重み \(A_i\)，白く塗るときは重み \(1\) とします． その後，\(N-1\) 回以下の操作をするとします．

• 同じ色の石を \(2\) つ選び，\(1\) つの石にマージする． 黒い石は必ず黒い石にマージされるが，白い石はマージ後に黒か白か選べる．

最終的に黒い石が \(1\) 個残る方法の数を数えればよいです．

各 \(0 \leq k \leq N\) に対し，最初に黒い石が \(k\) 個，白い石が \(N-k\) 個の場合に操作を行う方法が何通りあるか求めればよいです．

操作のたびに \(2\) つの石を選びますが，これらを右と左に対応させることにします．操作ごとに左右の選び方で \(2\) 通り発生しますが，これらの係数は最後にまとめて計算することにします．

操作の様子を \(2\) 分木で表すことにします． 左の石 \(l\) と右の石 \(r\) をマージして石 \(v\) になったとき，\(v\) の左/右の子を \(l,r\) とします．

この \(2\) 分木を数えることにします． \(2\) 分木の頂点に番号をつける（操作の順番に対応）ことに注意が必要です． 最初に石を一列に並べておき，隣接要素のマージを繰り返していくという操作で \(2\) 分木は作れます．

最初の \(N\) 個の石の色の並びを固定したとします． 石の色の並びが 黒，白，白，…，白，黒 となる部分をブロックと呼ぶことにします． 操作の様子を考えると，ブロックの内部と外部で操作が干渉することはないです． よって，各ブロックごとに操作を完了する方法の数を求めればよいです． なお，黒石ではなく，元の列の端で囲まれているような部分もブロックとみなすことができます． 両側を黒石で囲まれている場合と少し式は違いますが，やることはほとんど同じです．

例として，黒石がないブロック，つまり白石 \(N\) 個の状態からスタートして最終的に黒石 \(1\) 個になる方法の数を考えます．

白石 \(n+1\) 個からスタートして黒石 \(1\) 個を得る方法の数を \(f_n\) とおきます． 石の個数と \(f\) の添字がずれていますが，操作回数と添字を合わせると色々と便利なのでそうしています． \(f_n\) の指数的母関数 \(f(x)=\sum_{0 \leq n} f_n \times x^n/n!\) を考えます．

最後の操作に注目し，それが白石同士のマージなのか黒石同士のマージなのかで場合分けすると，\(f'(x)=1/(1-x)^2 + f^2(x)\) という微分方程式が得られます． ここまでわかれば，あとは分割統治+FFTを使えば \(O(N \log ^2N)\) で \(f_N\) を求めることができます． また，多項式のニュートン法を用いると \(O(N \log N)\) でも計算できます． これらの方法についてここでは解説しませんが，どちらについてもこちらの問題の解説が参考になります．

ブロックの片方の端だけ黒石のケースの答えの指数的母関数 \(g(x)\) を考えます． これも最後の操作に注目すると \(g'(x)=f(x)g(x)\) という微分方程式が得られて，解くことができます．

最後にブロックの両端が黒石のケースを考えます．これもまた最後の操作に注目することで \(h'(x)=g^2(x)\) がわかり，解けます．

黒石が \(k\) 個 (\(k>0\))，白石が \(N-k\) 個のケースを考えると，必要な値は \([x^{N-1}] g^2(x) h^{k-1}(x)\) だとわかります． これはまさに Power Projection と呼ばれる問題で，\(O(N \log^2N)\) 時間で解けることが知られています． この解説もまたここでは省略しますが，例えばこちらのブログが参考になります．

以上をすべて実装することで，\(O(N \log^2N)\) 時間でこの問題を解くことができます．

回答例(C++)