#P18573. Trading

Trading

Trading

一名交易者连续 nn 天交易加密货币。第 ii 天,每枚币的价格为 aia_i 美元。买入和卖出的币数均必须是整数。最初交易者没有币,但拥有足以进行任何购买的美元。

交易者严格遵守一个日程。日程是一个被标记为卖出日的日期集合。

  • 在未标记的日期,交易者可以按当天价格恰好买入一枚币,或者什么都不做。
  • 在标记的日期,交易者必须按当天价格至少卖出一枚币,卖出的数量不能超过当时持有的币数,并且当天不能买入。

给定日程下的一种策略,就是确定每天买入多少枚币(未标记日最多一枚)或卖出多少枚币(标记日至少一枚)。

固定价格数组 aa。如果在全部 2n2^n 种可能日程下的所有策略中,都不存在总利润更高的策略,就称交易者当前的策略是最优策略。总利润等于第 nn 天结束时的美元数减去第 11 天开始前的美元数,持有的币不计入利润。

现在给定一个日程。请计算有多少个长度为 nn、满足 1≤ai≤m1\le a_i\le m 的整数价格数组 aa,使得该日程下存在一种最优策略。答案对 998244353998244353 取模。

注意,最优性要与所有日程下的策略比较,不只是与给定日程下的其它策略比较;日程固定后仍可以选择未标记日不买入,也可以在卖出日卖出多枚币。

输入格式

第一行包含一个整数 tt(1≤t≤16951\le t\le1695),表示测试组数。

每组测试的第一行包含三个整数 n,m,kn,m,k(1≤n≤50001\le n\le5000,1≤m≤1091\le m\le10^9,0≤k≤n0\le k\le n),分别表示天数、价格上界和标记日期数。

若 k>0k>0,接下来一行包含 kk 个整数 d1<d2<⋯<dkd_1<d_2<\cdots<d_k(1≤di≤n1\le d_i\le n),表示卖出日,按严格递增顺序给出。

若 k=0k=0,这一行不存在。

一个输入文件中,所有测试的 nn 之和不超过 50005000。

输出格式

对每组测试输出一行一个整数,表示所求数组数对 998244353998244353 取模的结果。

样例

输入

4
2 2 1
2
3 2 1
2
3 3 0
1 5 1
1

输出

3
5
10
0

样例说明

第一组中,该日程只能在第 11 天买入一枚,在第 22 天卖出,利润为 a2−a1a_2-a_1。要达到所有日程下的最大利润,必须有 a2≥a1a_2\ge a_1。符合条件的数组为 (1,1)(1,1)、(1,2)(1,2)、(2,2)(2,2)。

第二组中,给定日程的利润为 a2−a1a_2-a_1。它必须不低于整个价格数组在所有日程下可取得的最大利润。符合条件的数组为 (1,1,1)(1,1,1)、(1,2,1)(1,2,1)、(1,2,2)(1,2,2)、(2,2,1)(2,2,1)、(2,2,2)(2,2,2)。

第三组中,k=0k=0,唯一可能达到最优的策略是什么也不做,利润为 00。这当且仅当数组非递增,即 a1≥a2≥a3a_1\ge a_2\ge a_3。符合条件的数组共有 1010 个。

第四组中,第 11 天就必须卖出币,但交易者最初没有币,标记日又不能买入。因此不存在任何有效数组。