#P9872. I. Colorings Counting

    ID: 8094 传统题 1000ms 512MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>CF2600组合数学数论模运算数学2023“钉耙编程”中国大学生算法设计超级联赛(7)

I. Colorings Counting

I. Colorings Counting

Problem Description

Given a ring of nn nodes. It's required to color each node with one of the colors in 0∼m−10 \sim m - 1, and ensure that adjacent points have different colors. Consider two colorings are different if and only if two colorings sequences a,ba, b cannot be transformed into each other through several of the following three operations:

  • Forall 1≤i≤n1 \le i \le n, a′[i]←a[i mod n+1]a'[i] \gets a[i \bmod n + 1], then a[i]←a′[i]a[i] \gets a'[i];
  • Forall 1≤i≤n1 \le i \le n, a′[i]←a[n−i+1]a'[i] \gets a[n - i + 1], then a[i]←a′[i]a[i] \gets a'[i];
  • Forall 1≤i≤n1 \le i \le n, a′[i]←(a[i]+1) mod ma'[i] \gets (a[i] + 1) \bmod m, then a[i]←a′[i]a[i] \gets a'[i]. Calculate the different colorings, modulo 998244353998244353.

Input

The input consists of multiple test cases. The first line contains a single integer TT (1≤T≤1001 \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,mn, m (4≤n≤10184 \le n \le 10 ^ {18}, 2≤m≤10182 \le m \le 10 ^ {18}). It's guaranteed that n,mn, m are not multiples of 998244353998244353. It's guaranteed that there will be no more than 4040 test cases with n,m>20n, m > 20. It's guaranteed that there will be no more than 2020 test cases with n,m>105n, m > 10 ^ 5. It's guaranteed that there will be no more than 55 test cases with n,m>1013n, m > 10 ^ {13}.

Output

For each test case, print a single integer - the different colorings, modulo 998244353998244353.

Sample Input

4
4 2
4 3
6 3
2023 808

Sample Output

1
2
5
304535191

Source

2023“钉耙编程”中国大学生算法设计超级联赛(7)