問題一覧 > 通常問題

No.1552 Simple Dice Game

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

問題文

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

f(X):=(Xの要素の最大値 −X の要素の最小値)×(X の各要素の和)

で定めます。

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

制約

  • 入力は全て整数
  • 1≤N≤1018
  • 1≤M≤5×105

入力

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

N M

出力

答えを mod998244353 で出力してください。

サンプル

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

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

  • f((1,1))=(1−1)×(1+1)=0
  • f((1,2))=(2−1)×(1+2)=3
  • f((2,1))=(2−1)×(2+1)=3
  • f((2,2))=(2−2)×(2+2)=0

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

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

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

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

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