>>804 の実装で一番早いのは
パスカルの三角形で縦に足して行くやり方の気がする