Tokitsukaze 有一个排列 $$$p$$$。她对 $$$p$$$ 执行了以下操作,恰好 $$$k$$$ 次:在一次操作中,对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$i$$$ 按顺序,如果 $$$p_i$$$ > $$$p_{i+1}$$$,则交换 $$$p_i$$$、$$$p_{i+1}$$$。经过$$$k$$$次运算后,时风得到了一个新的序列$$$a$$$,显然序列$$$a$$$也是一个排列。
之后,时风在纸上写下了$$$a$$$的值序列$$$v$$$。将长度为$$n$$$的排列$$$a$$$的值序列$$$v$$$表示为$$$v_i=\sum_{j=1}^{i-1}[a_i < a_j]$$$,其中$$$[a_i < a_j]$$$的值定义为$$$a_i < a_j$$$,则值为$$$1$$$,否则为$$$1$$$ $$$0$$$(换句话说,$$$v_i$$$ 等于位置 $$$i$$$ 左侧大于 $$$a_i$$$ 的元素数量)。然后时风就出去工作了。
时风家里有三只淘气的猫。回到家后,她发现价值序列为$$$v$$$的纸被猫咬掉了,留下了几个洞,以至于有些位置的价值看不清。她忘记了原来的排列 $$$p$$$ 是什么。她想知道有多少种不同的排列$$$p$$$,以便恰好经过$$$k$$$运算后的新排列$$$a$$$的值序列$$$v$$$与纸上写的$$$v$$$相同(不考虑不清楚的位置)。
由于答案可能太大,请打印 $$$998\,244\,353$$$ 模。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。每个测试用例由两行组成。
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^6$$$; $$$0 \leq k \leq n-1$$$) - 排列的长度和确切的操作次数。
第二行包含 $$$n$$$ 整数 $$$v_1, v_2, \dots, v_n$$$ ($$$-1 \leq v_i \leq i-1$$$) — 值序列 $$$v$$$。 $$$v_i = -1$$$ 表示$$$v$$$的第$$$i$$$位置看不清。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,打印一个整数 - 不同排列的数量以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 5 0 0 1 2 3 4 5 2 -1 1 2 0 0 5 2 0 1 1 0 0
输出 #1
1 6 6
注意
在第一个测试用例中,只有排列 $$$p=[5,4,3,2,1]$$$ 满足约束条件。
在第二个测试用例中,满足约束条件的排列有$$$6$$$,分别是:
- $$$[3,4,5,2,1]$$$ $$$\rightarrow$$$ $$$[3,4,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[3,5,4,2,1]$$$ $$$\rightarrow$$$ $$$[3,4,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[4,3,5,2,1]$$$ $$$\rightarrow$$$ $$$[3,4,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[4,5,3,2,1]$$$ $$$\rightarrow$$$ $$$[4,3,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[5,3,4,2,1]$$$ $$$\rightarrow$$$ $$$[3,4,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[5,4,3,2,1]$$$ $$$\rightarrow$$$ $$$[4,3,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
因此,经过 $$$2$$$ 次交换后,它们都将变为 $$$a=[3,2,1,4,5]$$$,其值序列为 $$$v=[0,1,2,0,0]$$$。