問題一覧 > 通常問題

No.3571 Sigma Problems Problem

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 30
作問者 : kazuppa / テスター : ゆにたりー卿 👑 loop0919 ぽえ
お気に入りにしたユーザー ProblemId : 11950 / 自分の提出
問題文最終更新日: 2026-06-11 00:05:39
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

Introduction

This problem was rejected from The 2nd Iwai Seijin Anthology Programming Contest Div.1.

kazuppa instead set Make 81181819 with only 0,1,or 8, so please check that one out as well.

Problem Statement

Consider the following problem (hereafter called the sub-problem).

You are given an integer sequence $A$ of length $N$ and a positive integer $M$. All elements of $A$ are at least $0$ and less than $M$.

Also, define $f(x,y)=(x+y)\bmod M$.

Find $\displaystyle\sum_{i=1}^{N-1} \displaystyle\sum_{j=i+1}^{N}f(A_i,A_j)$.

You are given positive integers $N,M$.

There are $M^N$ sequences $A$ satisfying the conditions. Find the sum of the answers to all of these sub-problems, modulo $998244353$ (hereafter, this problem is called the main problem).

You are given $T$ test cases; solve all of them.

Input

$T$
$Testcase_1$
$Testcase_2$
$\vdots$
$Testcase_T$
Each test case is given in the following format.
$N\ M$

Constraints

  • $1\leq T\leq 10^5$
  • $1\leq N,M\leq 10^{18}$
  • All input values are integers.

Output

On the $i$-th line, output the answer to the $i$-th test case.

Print a newline at the end.

Sample

Sample 1
Input
5
3 2
8 8
169 231
411 892
1000000000000000 1000000000000000
Output
12
645922815
435837943
117185670
917198649

Let us explain test case 1.

For example, when $A=(1,0,1)$,

$f(A_1,A_2)=(1+0)\bmod 2=1$

$f(A_1,A_3)=(1+1)\bmod 2=0$

$f(A_2,A_3)=(0+1)\bmod 2=1$

Thus, the answer to this sub-problem is $1+0+1=2$.

Continuing in the same way, the answer to the main problem is $0+2+2+2+2+2+2+0=12$.

Note that the answer to the sub-problem is not taken modulo $M$. Also note that the answer to the main problem should be output modulo $998244353$.

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