|
||||||||||
I. Colorings CountingTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 10 Accepted Submission(s): 8 Problem Description Given a ring of $n$ nodes. It's required to color each node with one of the colors in $0 \sim m - 1$, and ensure that adjacent points have different colors. Consider two colorings are different if and only if two colorings sequences $a, b$ cannot be transformed into each other through several of the following three operations: - Forall $1 \le i \le n$, $a'[i] \gets a[i \bmod n + 1]$, then $a[i] \gets a'[i]$; - Forall $1 \le i \le n$, $a'[i] \gets a[n - i + 1]$, then $a[i] \gets a'[i]$; - Forall $1 \le i \le n$, $a'[i] \gets (a[i] + 1) \bmod m$, then $a[i] \gets a'[i]$. Calculate the different colorings, modulo $998244353$. Input The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 100$) - the number of test cases. Description of the test cases follows. The first line of each test case contains two integer $n, m$ ($4 \le n \le 10 ^ {18}$, $2 \le m \le 10 ^ {18}$). It's guaranteed that $n, m$ are not multiples of $998244353$. It's guaranteed that there will be no more than $40$ test cases with $n, m > 20$. It's guaranteed that there will be no more than $20$ test cases with $n, m > 10 ^ 5$. It's guaranteed that there will be no more than $5$ test cases with $n, m > 10 ^ {13}$. Output For each test case, print a single integer - the different colorings, modulo $998244353$. Sample Input
Sample Output
Source | ||||||||||
|