最終的な合計から逆順に積み重ねていくとパスカルの三角形のような形になる.

よって, 最終的な合計は,

\[\sum_{k=1}^{N} {}_{N-1}C_{k-1} a_k\]

となる.

階乗と逆元はあらかじめ計算しておく.