#P9832. Data Generation

    ID: 8054 传统题 1000ms 64MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1800普及+/提高-指示变量期望线性性全概率公式线性递推模逆元快速幂2023“钉耙编程”中国大学生算法设计超级联赛(4)

Data Generation

Data Generation

Problem Description

Yoshinow2001 is making data for his problem. He wants to generate a random permutation of {0,…,n−1}\lbrace 0,\dots,n-1\rbrace , so he used the following algorithm:

ans = 0
for i = 0, ..., n-1: a[i] = i
repeat m times:
    choose i and j independently and uniformly from 0, ..., n-1
    swap(a[i], a[j])
for i = 0, ..., n-1:
    if a[i] != i: ans = ans + 1

The two indices may be equal. All draws are independent.

Original algorithm diagram Now Yoshinow2001 is concerned that this algorithm is not random enough ------ after all, if you want to randomize a permutation, the expected number of elements for ai≠ia_i\neq i should be n−1n-1. So he wants to ask what the mathematical expectation of the final ansans is.

Input

The first line of input is a positive integer T(1≤T≤105)T(1\leq T\leq 10^5) representing the number of data cases. For each cases consists of a single line of two integers n,mn,m, separated by a space. Where 1≤n≤10181\leq n\leq 10^{18},0≤m≤10180\leq m\leq 10^{18}, ensure that nn is not a multiple of 998 244 353998\ 244\ 353.

Output

For each test case, print one integer in [0,998244353)[0,998244353) representing the expected value of ansans modulo 998244353998244353. If the expectation is p/qp/q in lowest terms, print pq−1 mod 998244353p q^{-1}\bmod 998244353.

Sample Input

3
1 0
1 1
2 1

Sample Output

0
0
1

Source

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