作問者より

・C問題とは、制約と実行制限時間のみが異なります。
・python,pypyでのACは確認していますが、低速な言語では実装次第で間に合わない可能性があります。

問題文

3つの要素から成る数列 $v=(a_1,a_2,a_3)$ が次の条件を満たす時， $v$ は門松列であると言い伝えられています。
1.$a_1,a_2,a_3$ は全て異なる
2.3つの要素のうち $a_2$ が最も大きい，あるいは最も小さい
さらに, $n$ 個の要素(ただし $3≦n$) から成る数列$ w=(a_1,a_2....,a_n)$ が
どの連続した3つの要素を取り出しても門松列であるとき $w$ は門松列列であると言います。

長さ $N$ の整数列であって、数列の各要素が $0$ 以上 $K$ 未満であるものは $K^N$ 通りありますが、そのうち門松列列であるものが $ans_1$ 通りであるとします。$ans_1$を $998244353$ で割った余りを出力してください。
さらに、 $ans_1$ 通りの門松列列すべてにおいて、それぞれ数列の和を計算し、合計したものを $ans_2$ とします。 $ans_2$ を $998244353$ で割った余りを出力してください。

入力

$N\ K$

$3≦N≦10^9$
$3≦K≦9$
$N,K$ は整数である。

出力

$ans_1$と$ans_2$をそれぞれ$998244353$で割った余りを半角スペース区切りで出力してください。
最後に改行してください。

サンプル

3 3

4 12

6 9

26124 626976

75432 9

27800053 805337678