You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

根据 这题 我们知道了两个排列可以进行运算。但你显然做不出这么复杂的运算，所以规定两个排列的乘法运算：若 $r=p\cdot q$，则 $r_i=p_i\cdot q_i$，也就是逐项相乘。

$p,q$ 是排列，而本题中 $q$ 是最简单的排列：$q_i=i$。$r$ 不一定是排列，但是我们希望 $r$ 是单调不降的。请问有多少排列 $p$ 使得 $p\cdot \{1,2,\dots,n\}$ 得到的序列单调不降？答案对 $998\ 244\ 353$ 取模。

特殊地，对于给定的一组 $x,y$，排列 $p$ 需要满足 $p_x=y$。当 $x=y=-1$ 时，则无此限制。

输入格式

第一行输入一个整数 $T$，表示数据组数。

对于每组数据，唯一的一行输入三个整数 $n,x,y$。

输出格式

对于每组数据，输出一个整数表示答案对 $998\ 244\ 353$ 取模后的结果。

3
2 -1 -1
3 -1 -1
100 -1 -1

2
3
246748276

5
2 1 2
5 3 2
10 3 3
100 100 100
1000 1000 1

1
2
42
494958974
0

提示

样例解释 1

本样例中所有数据均不对排列做其他限制，即 $x=y=-1$。

当 $n=2$ 时，所有排列都符合要求。

当 $n=3$ 时，符合要求的排列有 $\{1,2,3\}$，$\{1,3,2\}$，$\{2,1,3\}$。

样例解释 2

本样例中所有数据均对排列中某一个位置的数做了限制，即 $x,y\neq-1$。

$n=2,p_1=2$ 时，符合要求的排列仅有 $\{2,1\}$。

$n=5,p_3=2$ 时，符合要求的排列有 $\{1,3,2,4,5\}$，$\{1,3,2,5,4\}$。

数据范围

$1\le T\le 10^6$，$1\le n\le 2\cdot10^6$。注意， $\sum n$ 可以很大。

$x=y=-1$ 或 $1\le x,y\le n$。

本题采用捆绑测试。

• Subtask 1：$T\le 100,n\le 8$。共 $5$ 分。
• Subtask 2：$\sum n\le2\cdot10^6,x=y=-1$。共 $20$ 分。
• Subtask 3：$\sum n\le 2\cdot 10^6$。共 $20$ 分。
• Subtask 4：$x=y=-1$。共 $20$ 分。
• Subtask 5：无特殊限制。共 $35$ 分。

如果你过了这题发现可以优化并且闲得很，可以到$\small\color{blue}{这}$做加强版。加强版的数据范围是 $1\le T\le 10^6,1\le n\le10^{18}$。

输入输出量巨大，不使用快读快写而超时是你活该概不负责。