题目描述

给定 $T,n,m$，你需要回答 $T$ 次询问。每次询问给定 $A,B$。

定义一个值域在 $[1,m]$ 中的 $n$ 元组 $a[1,n]$ 合法，当且仅当这 $n$ 个数满足：

并且

定义一个 $n$ 元组的权值为：

你需要求出所有合法 $n$ 元组的权值和。由于答案可能很大，请输出其对 $998244353$ 取模后的结果。

输入格式

第一行包含三个正整数 $T,n,m$。

接下来 $T$ 行，每行包含两个正整数 $A,B$。

输出格式

对于每次询问，输出一行一个整数，表示权值和对 $998244353$ 取模后的结果。

样例 1 输入

3 2 4
1 4
1 2
2 3

样例 1 输出

100
75
83

数据范围

对于所有数据：

• $1\le T\le 5\times 10^5$；
• $1\le n\le 10^9$；
• $1\le A,B\le m\le 3\times 10^5$。

特殊性质：

• A：$A=1$；
• B：$B=m$；
• C：$B=1$。