No.1552 Simple Dice Game
タグ : / 解いたユーザー数 110
作問者 :
nok0
/ テスター :
kyoprouno
unyon_maru65536
Problem Statement
Define a map $f$ from integer sequences $X$ to integers by
$f(X):=(X$'s maximum element $-X$'s minimum element$)\times(X$'s sum of elements$)$
.
There are $M^N$ possible sequences $A$ of length $N$ whose elements are all integers between $1$ and $M$, inclusive. Find the sum of $f(A)$ over all of them, modulo $\bmod{998244353}$.
Constraints
- All inputs are integers.
- $1 \le N\le 10^{18}$
- $1 \le M\le 5\times 10^5$
Input
The input is given from standard input in the following format.
$N\ M$
Output
Output the answer modulo $\bmod998244353$.
Sample
Sample 1
Input
2 2
Output
6
There are $4$ possible sequences for $A$: $(1,1),(1,2),(2,1),(2,2)$.
- $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$
Therefore, the sum of $f(A)$ is $6$.
Sample 2
Input
2 4
Output
100
Sample 3
Input
10 1
Output
0
Sample 4
Input
1000000000000000000 500000
Output
8687250
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。