問題一覧 > 通常問題

No.2670 Sum of Products of Interval Lengths

レベル : / AI推定難易度 : 2650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 27
作問者 : suisen / テスター : cureskol ygussany kaichou243
お気に入りにしたユーザー ProblemId : 10305 / 自分の提出
問題文最終更新日: 2024-02-11 22:17:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 420 (順位表) の他の問題:

Problem Statement

You are given positive integers $n,m$.

For an integer sequence $A = (A _ 1, A _ 2, \ldots, A _ n)$ of length $n$ whose elements are all integers between $1$ and $m$, inclusive, a pair of integers $(l,r)$ satisfying $1\leq l\leq r\leq n$ is called a good pair if the following holds.

  • $A _ {l + i} = A _ l + i$ holds for all $i = 0, 1, \ldots, r - l$

Also, an integer sequence $(x _ 1, x _ 2, \ldots, x _ k)$ is called a good sequence if both of the following $2$ conditions hold.

  • $1 = x _ 1\lt x _ 2\lt \cdots \lt x _ k = n + 1$
  • For all $i = 1,2,\ldots,k - 1$, the pair $(x _ i, x _ {i + 1} - 1)$ is a good pair

It can be proved that for any $A$, the good sequence $x$ of minimum length is uniquely determined; denote it by $x ^ \ast = (x ^ \ast _ 1, x ^ \ast _ 2, \ldots, x ^ \ast _ k)$. Then, the score $f(A)$ of $A$ is defined as follows.

$$f(A)\coloneqq\prod _ {i = 1} ^ {k - 1} (x ^ \ast _ {i + 1} - x ^ \ast _ i).$$

There are $m ^ n$ integer sequences $A$ of length $n$ whose elements are all integers between $1$ and $m$, inclusive. Find the sum of the scores over all of them, modulo $998244353$.

Input

The input is given from standard input in the following format.

$n\ m$
  • All input values are integers.
  • $1\leq n\leq 2\times 10 ^ 5$
  • $1\leq m\leq 10 ^ {18}$

Output

Print the answer on $1$ line, followed by a newline.

Sample

Sample 1
Input
3 2
Output
12

This input represents $n=3,\ m=2$. There are $8$ possible sequences $A$: $(1,1,1),\ (1,1,2),\ (1,2,1),\ (1,2,2),\ (2,1,1),\ (2,1,2),\ (2,2,1),\ (2,2,2)$.

For example, for $A = (1,1,2)$, there are $2$ good sequences, $x = (1,2,3,4)$ and $x = (1,2,4)$, and the one of minimum length is $x ^ \ast = (1,2,4)$. Therefore, the score of this $A$ is $(2 - 1) \times (4 - 2) = 2$.

It can be verified that the scores of $(1,1,1),\ (1,1,2),\ (1,2,1),\ (1,2,2),\ (2,1,1),\ (2,1,2),\ (2,2,1),\ (2,2,2)$ are $1,2,2,2,1,2,1,1$, respectively, so print their sum, $12$, as the answer.

Sample 2
Input
200000 1000000000000000000
Output
156232207

Print the sum of the scores modulo $998244353$.

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