Faulhaber's formula

解説？

mod 998244353 で $K$ 番目までのベルヌーイ数を求めることができればファウルハーバーの公式から答えを $O(K)$ で求めることができるらしいです。自身のコードがうまくいかなかったのは正規化を知らないからっぽい

時間計算量はベルヌーイ数の列挙がボトルネックとなり、$O(K^2)$ または $O(K)$ です。

参考

• sounansya ベルヌーイ数を線形時間で求める (ベルヌーイ数を $O(K)$ で求められるらしい) https://qiita.com/sounansya/items/0f40351743ef6eecf21a

• yaketake08 ベルヌーイ数 (Bernoulli number) (愚直にやってもベルヌーイ数を $O(K^2)$ で求められるらしい) https://tjkendev.github.io/procon-library/python/math/bernoulli-number.html