题目背景

cyx 仰慕 rainboy 跌宕起伏的 rating 变化线。

题目描述

cyx 最近打了 $n$ 场 czoj，其 performance 分别为 $a_1,a_2,\dots,a_n$。为了学习 rainboy 上上下下的 rating 变化风格，他规定一次 performance 是优美的当且仅当这一次和相邻的两次 performance（记为 $a_{i-1},a_i,a_{i+1}$）满足峰形或者谷形。形式化地，$(a_{i-1}-a_i)(a_{i+1}-a_i)>0$。注意，第一次和最后一次的 performance 永远不是优美的。

cyx 作为 czoj 管理员可以决定将一些比赛记录隐藏，剩下一个非空子序列使得序列中“优美的”performance 个数恰好在区间 $[l,r]$ 之间，且相邻两次 performance 不相同。cyx 想知道有多少本质不同的子序列满足条件。

再次提醒，要求相邻两次 performance 不相同。

答案需要对 $99\bf{3}$ $244\ \bf{8}$$53$ 取模。

输入格式

本题单个测试点内有多组数据。

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

接下来的 $T$ 组数据，每组第一行三个非负整数 $n,l,r$，第二行 $n$ 个正整数 $a_i$ 表示 performance 序列。

输出格式

对于每组测试数据，输出一个取模过的整数表示答案。

样例

4
3 0 1
1 2 1
4 0 0
1 4 2 3
6 1 1
1 3 4 2 5 3
10 1 3
5 2 8 8 4 2 2 9 1 4

5
11
20
151

对于第一组测试数据，可以保留子序列 $\{1\}$，$\{2\}$，$\{1,2\}$，$\{2,1\}$。这些子序列都不存在优美的 performance。也可以保留子序列 $\{1,2,1\}$，恰有 $1$ 个 performance （$a_2=2$）是优美的，也满足条件。

数据规模与约定

本题采用捆绑测试。各子任务时限不同。

• Subtask 0（3 pts）：时限 $\text{2s}$，$a_i$ 单调递增。
• Subtask 1（5 pts）：时限 $\text{0.5s}$，$n \leq 15$。
• Subtask 2（25 pts）：时限 $\text{0.5s}$，$n \leq 300$。
• Subtask 3（19 pts）：时限 $\text{5s}$，$a_i$ 互不相同。
• Subtask 4（9 pts）：时限 $\text{5s}$，存在 $1\le p\le n$ 使得 $a_1<a_2<\dots<a_{p-1}<a_n<a_{n-1}<\dots<a_p$。
• Subtask 5（39 pts）：时限 $\text{5s}$，无特殊限制。

对于 $100\%$ 的数据，保证 $2 \leq n \leq 5000$，$0 \leq l\leq r\leq \min(n-2,100)$，$1\le a_i\le10^9$，$1\le T\le5$。

注意：时限很大不意味着可以为所欲为！其实是出题人丑陋的【数据删除】算法常数过大，但是又想放掉。 如果还觉得卡常，那么你有什么实力啊，菜就多练改进算法吧。