Sum of Tree Values in Varying Morphologies

There is a quirky live‐streamer who loves to slack off and today he decides to stream from the most melancholic tree in Fish World. This tree is extremely languid – it has no root – but it consists of n nodes labeled from 1 to n and n-1 edges connecting them (i.e. a tree in the usual sense). However, the tree can transform its morphology – its edges may shift, vanish, or even new ones grow – as long as the graph remains connected and always has exactly n-1 edges (thus the different morphologies are simply all spanning trees on n labeled nodes, and there are n^(n-2) of them by Cayley’s formula).

For any given tree (morphology), let k be the number of edges (u,v) satisfying \[ |u-v|=1, \] and let its value be defined as \[ \text{value} = k \times c^k. \]

The task is to compute the sum of the values of all different tree morphologies modulo 998244353. Note that if a tree has more than one such edge, its value is multiplied accordingly. Also note that a tree’s contribution is k*c^k (not c^k).

Since there are multiple test cases, you are given an integer t on the first line, followed by t test cases. Each test case consists of two integers n and c.

Input Format (detailed below):

 t
 n c
 n c
 ...

Output Format: For each test case, output one line containing the required sum modulo 998244353.

Note: Even though one could think of approaching this problem directly using Kirchhoff's Matrix‐Tree Theorem with weighted edges, a combinatorial inclusion–exclusion method leads to the following final formula:

[ \text{answer} = c \times \sum_{k=1}^{n-1} (-1)^{k+1} ; k ; n^{n-k-2} ; (1-c)^{k-1} ; S(n,k) \mod 998244353, ]

where \[ S(n,k) = \sum_{r=1}^{\min(k, n-1)} \binom{n-k}{r} \; F(r,k), \]

and F(r,k) is defined via the recurrence (over compositions of k into r parts):

[ F(r,k) = \sum_{L=1}^{k} (L+1) ; F(r-1, k-L),\quad F(0,0)=1,;F(0,k)=0; (k>0). ]

You may assume that n is small enough (for example, n\,\le\,200) so that an O(n³) solution will pass.

inputFormat

The input begins with an integer t (1 ≤ t ≤ 100), the number of test cases. Then for each test case, a line contains two integers n and c (with 1 ≤ n ≤ 200 and 1 ≤ c ≤ 10⁹).

 t
 n c
 n c
 ...

outputFormat

For each test case, output a single integer – the sum of the values of all spanning trees (each tree’s value is defined as k * c^k where k is the count of edges (u,v) with |u-v|=1), taken modulo 998244353.

sample

1
2 3

3