問題一覧 > 通常問題

No.1552 Simple Dice Game

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 86
作問者 : nok0nok0 / テスター : kyoprounokyoprouno unyon_maru65536unyon_maru65536
4 ProblemId : 6486 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-19 00:23:10

問題文

整数列 $X$ から整数への写像 $f$ を

$f(X):=(X$の要素の最大値 $-X$ の要素の最小値$)\times(X$ の各要素の和$)$

で定めます。

長さ $N$ の数列 $A$ であって各要素が $1$ 以上 $M$ 以下の整数であるものは $M^N$ 通り考えられますが、それら全てについての $f(A)$ の総和を $\bmod{998244353}$ で求めてください。

制約

  • 入力は全て整数
  • $1 \le N\le 10^{18}$
  • $1 \le M\le 5\times 10^5$

入力

入力は以下の形式で標準入力から与えられます。

$N\ M$

出力

答えを $\bmod998244353$ で出力してください。

サンプル

サンプル1
入力
2 2
出力
6

$A$ として考えられる数列は $(1,1),(1,2),(2,1),(2,2)$ の $4$ 種類です。

  • $f((1,1)) = (1-1)\times (1 + 1 ) = 0$
  • $f((1,2)) = (2-1)\times (1 + 2 ) = 3$
  • $f((2,1)) = (2-1)\times (2 + 1 ) = 3$
  • $f((2,2)) = (2-2)\times (2 + 2 ) = 0$

以上より、 $f(A)$ の総和は $6$ です。

サンプル2
入力
2 4
出力
100

サンプル3
入力
10 1
出力
0

サンプル4
入力
1000000000000000000 500000
出力
8687250

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。