问题 I: Colorings Counting

Given a ring of n nodes. It's required to color each node with one of the colors in 0∼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:

Calculate the different colorings, modulo 998244353.

The first line of each test case contains two integer n, m (4≤n≤1018, 2≤m≤1018).

It's guaranteed that n, mare 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>1013.