毎日格上の問題を倒すやつの22日目です。

問題リンク

問題概要

集合の列に対して、隣り合う要素で片方にしかないものがちょうど1つであるものを、「素晴らしい整数の列」とするよ。

また、「素晴らしい整数の列」のスコアを、 $i$ を含む集合の個数をすべての $i$ に対して求めたものの総積とするよ。

すべての「素晴らしい整数の列」のスコアの和を $998244353$ で割ったあまりを求めてね。

長さ $N-1$ の数列を決めると、天才ができます。

最初の集合は $2^{M-1}$ 通りですが、これらすべてに対するスコアの和が $N^M$ になることが証明できます。

なので、これと数列の数の積が答えです。¹

MOD=998244353
N,M=map(int,input().split())
print((pow(N,M,MOD)*pow(M,N-1,MOD))%MOD)

天才をするの気持ちいいよね