タイトルの通り, ベルヌーイ数を求めてそこから計算する.

ベルヌーイ数の求め方は以下の通り.

\[B_0 = 1 \\ B_n = -\frac{1}{n+1}\sum_{k=0}^{n-1}\binom{n+1}{k}B_k\]

ベルヌーイ数を求めた後, 和は以下の式で計算できる.

\[\begin{align} S_k(n) &= \sum_{j=0}^{n-1} n^k \\ &= \frac{1}{k+1}\sum_{j=0}^k\binom{k+1}{j}B_jn^{k-j+1} \end{align}\]

二項係数を計算するために階乗と逆元はあらかじめ計算しておく.

これでも時間はギリギリなので, 奇数番目のベルヌーイ数は0になることを利用して計算を省くなりしないと通らなかった.