Simple Score Sum

2 secs 1024 MB
sgsw

問題文


自然数が与えられます.

長さの整数列のうち,すべての要素が以上以下の数列の集合をとします.

また,整数列に対して,その数列のスコアを以下で定めます.


ならば.

ならば,以下で定まる長さの数列をとし,.


さて,

としたときで割ったあまりを求めてください.


制約


入力


入力は以下の形式で与えられます.

N M

出力


で割ったあまりを求めてください.

最後に改行してください.

サンプル


入力1
3 2
出力1
48
入力2
2022 222
出力2
603761734
入力3
123456789123456789 123456789123456789
出力3
806747933

オーバフローに注意してください.

提出


Go (1.14)