#P18573. Trading
Trading
Trading
一名交易者连续 天交易加密货币。第 天,每枚币的价格为 美元。买入和卖出的币数均必须是整数。最初交易者没有币,但拥有足以进行任何购买的美元。
交易者严格遵守一个日程。日程是一个被标记为卖出日的日期集合。
- 在未标记的日期,交易者可以按当天价格恰好买入一枚币,或者什么都不做。
- 在标记的日期,交易者必须按当天价格至少卖出一枚币,卖出的数量不能超过当时持有的币数,并且当天不能买入。
给定日程下的一种策略,就是确定每天买入多少枚币(未标记日最多一枚)或卖出多少枚币(标记日至少一枚)。
固定价格数组 。如果在全部 种可能日程下的所有策略中,都不存在总利润更高的策略,就称交易者当前的策略是最优策略。总利润等于第 天结束时的美元数减去第 天开始前的美元数,持有的币不计入利润。
现在给定一个日程。请计算有多少个长度为 、满足 的整数价格数组 ,使得该日程下存在一种最优策略。答案对 取模。
注意,最优性要与所有日程下的策略比较,不只是与给定日程下的其它策略比较;日程固定后仍可以选择未标记日不买入,也可以在卖出日卖出多枚币。
输入格式
第一行包含一个整数 (),表示测试组数。
每组测试的第一行包含三个整数 (,,),分别表示天数、价格上界和标记日期数。
若 ,接下来一行包含 个整数 (),表示卖出日,按严格递增顺序给出。
若 ,这一行不存在。
一个输入文件中,所有测试的 之和不超过 。
输出格式
对每组测试输出一行一个整数,表示所求数组数对 取模的结果。
样例
输入
4
2 2 1
2
3 2 1
2
3 3 0
1 5 1
1
输出
3
5
10
0
样例说明
第一组中,该日程只能在第 天买入一枚,在第 天卖出,利润为 。要达到所有日程下的最大利润,必须有 。符合条件的数组为 、、。
第二组中,给定日程的利润为 。它必须不低于整个价格数组在所有日程下可取得的最大利润。符合条件的数组为 、、、、。
第三组中,,唯一可能达到最优的策略是什么也不做,利润为 。这当且仅当数组非递增,即 。符合条件的数组共有 个。
第四组中,第 天就必须卖出币,但交易者最初没有币,标记日又不能买入。因此不存在任何有效数组。