提供一个 $\mathrm{O}(Tn^3m)$ 的做法，目前在各 oj 上是 rank 1，运行时间为第二名的 $\frac{1}{6}$ 以内。
类似于本题解的方法不建议在考试中使用，非常耗时间。并且公式很丑。
坐稳了！！
Step 1
@Alex_Wei 已经把严谨的结构刻画讲清楚了，这里再写一下自己的理解（本质上是等价的），看起来不大优美，但比较直观。
对于一个完整的序列 $a_{1\cdots n}$，找出其最长的前缀 $a_{1\cdots r}$，满足：前缀中 $\le a_r$ 的数严格递增，$\ge a_r$ 的数严格递减，类似于形成一个尖角。接下来暂时默认 $r<n$。
如果 $a_{r+1}=a_r$，那么要求 $a_{r+1\cdots n}$ 中，$\le a_r$ 的数严格递减，$\ge a_r$ 的数严格递增。这种情况恰好有 $2$ 种染色方案且得分相同。
否则，记 $a_{1\cdots r}$ 中最大的 $<a_r$ 的数为 $D$（不存在则为 $0$），最小的 $>a_r$ 的数为 $U$（不存在则为 $m+1$），不妨设 $a_{r+1}\le D$（与之对称的一种情况是 $\ge U$）。现在找到以 $a_{r+1}$ 开头的最长严格递减子段，如果子段末尾还有下一项，则记为 $a_s$，否则肯定是完美的。
结论：此时完美数组的充要条件是，在 $a_{r+1\cdots n}$ 中，$\le a_{r+1}$ 的数严格递减，不存在 $(a_{r+1},a_r]$ 以内的数，且 $\ge a_s$ 的数严格递增。
如图，这是一个完美数组的例子（横坐标为下标，纵坐标为值）：
它共有 $4$ 种染色方案，分别对应着下图中全不选/选一个黄色点染成绿色，其他黄色点染成红色：
如果 $a_s\in (D,a_r]$，那么只有 $1$ 种染色方案，以下是一例；如果 $a_s\in (a_{r+1},D]$ 则无染色方案。
同时，通过观察例子，可以发现多种染色方案一定是形如：一段前后缀颜色固定，中间剩下的区间，它有一个染色方案是全染红/绿，其余方案仅通过选其中某一个反转颜色得到。若 $a_{r+1}\le D$，则允许变颜色的点是以 $(a_U^{-1},U)$ 为左上角，$(r+1, a_{r+1})$ 为右下角的矩形以内的点。这部分实际上是递增的，且相对值域是连续的。$a_{r+1}\ge U$ 类似。
以上的证明都是容易的，需要一些分类讨论。
考虑哪种染色方案得分最大，容易发现最后一个可以变的点变色一定比其他点变色更优。因此最优染色一定是：$a_{1\cdots r-1}$ 中 $<a_r$ 的和 $a_{r+1\cdots n}$ 中 $>a_r$ 的染红色，$a_{1\cdots r-1}$ 中 $>a_r$ 的和 $a_{r+1\cdots n}$ 中 $<a_r$ 的染绿色，$a_r$ 两种均有可能。
Step 2
下文中 $r,U,D$ 的含义不变。称出现了满足 $a_{r+1}=a_r$ 或 $\le D$ 或 $\ge U$ 的情况为“交叉”，$a_r$ 为“交叉点”。称 $a_{1\cdots t}$ 为“前面”，$a_{t+1\cdots n}$ 为“后面”。组合数里只要有负数结果就是 $0$，除了 $\binom{-1}{-1}=1$。
回到原问题。先来道开胃菜：前面已经交叉了。这时可以由 $a_{1\cdots t}$ 确定后面染绿部分必须要小于某个值 $L$，染红部分必须要大于某个值 $R$。
枚举后面有 $i$ 个染绿的。方案数为： $$ \binom{L-1}{i}\binom{m-R}{n-t-i}\binom{n-t}{i} $$ 得分贡献为： $$ \begin{aligned} &\left[\sum_{j<L}\sum_{k\le t}[a_k<j]j\right]\binom{L-2}{i-1}\binom{m-R}{n-t-i}\binom{n-t}{i}\\ +{}&\left[\sum_{j>R}\sum_{k\le t}[a_k>j](m-j+1)\right]\binom{L-1}{i}\binom{m-R-1}{n-t-i-1}\binom{n-t}{i} \end{aligned} $$ 可以共 $\mathrm{O}(n+m)$ 计算。另外需要求前面的贡献，可以用树状数组。
Step 3
前面尚未交叉时，为了简化起见，分 $a_r;\fbox{</=/>};a_t$ 讨论。$a_r=a_t$ 也就是 $r=t$，这时暴力枚举 $a_{r+1}$ 后套用 Step 2 方法，时复只有两次方。
$a_r>a_t$ 与 $a_r<a_t$ 的算法完全相同。下记 $L$ 为前面最大的 $<a_t$ 的数（不存在则为 $0$），$R=a_r$，$X$ 为前面 $\le L$ 的数的个数，$Y=t-X$。
求方案数可以用 dp。交叉之前，想象“识别尖角”的过程，每次新加入的 $a$ 允许处于两个区间中：
实际计数时，只需要钦定一个区间就行了，一般不会计重。于是 $f_{i,j,k}$ 表示，交叉之前，$a_i=j$，区间另一个端点为 $k$ 的方案数。一种转移是枚举 $a_{i+1}$，然后转移到 $f_{i,a,j/k}$。
$g_{i,j,k}$ 表示交叉之后，上一个染绿的为 $j$ ，上一个染红的为 $k$ 的方案数，转移略。$f$ 在 $i$ 作为 $r$ 时要转移给 $g$，为了避免信息不够无法转移以及计重的情况，$j>k$ 的 $f_{i,j,k}$ 只枚举 $a_{i+1}\le k$ 以及 $a_{i+1}=a_i$ 的情况进行贡献，$j<k$ 的只枚举 $a_{i+1}\ge k$ 的情况进行贡献。
以上 dp 均可以用前缀和优化做到 $\mathrm{O}(nm^2)$，但是这个 dp 无法类推求出得分和，我们放弃 dp，尝试直接推式子。同样地，还是只考虑 $a_{r+1}\le D$、 $a_{r+1}=a_r$ 以及 $r=n$ 的情况，$a_{r+1}\ge U$ 情况可以将 $a_i\mapsto m-a_i+1$ 后套用 $a_{r+1}\le D$ 的算法。
首先，后面的结构大致包含这些要素：交叉前 $<a_r$ 的数个数、交叉前 $>a_r$ 的数个数、$r$、$a_r$、$a_{r+1}$、交叉后 $<a_r$ 的数个数、交叉后 $>a_r$ 的数个数。考虑枚举其中一些。
对于 $a_{r+1}\le D$，枚举交叉前 $<a_r$ 的数个数 $i$，交叉前 $>a_r$ 的数个数 $j$，交叉后 $<a_r$ 的数个数 $k$，方案数为： $$ \begin{aligned} &\sum_{a_r}\sum_{D<a_r}\textcolor{red}{\binom{D-L-1}{i-1}\binom{m-a_r}{n-t-i-j-k-1}}\textcolor{green}{\binom{D}{k}\binom{R-a_r-1}{j}}\textcolor{blue}{\binom{i+j}{i}\binom{n-t-i-j-2}{k-1}}\\ ={}&\binom{i+j}{i}\binom{n-t-i-j-2}{k-1}\sum_{a_r}\left[\sum_{D<a_r}\binom{D-L-1}{i-1}\binom{D}{k}\right]\binom{R-a_r-1}{j}\binom{m-a_r}{n-t-i-j-k-1}\\ ={}&\binom{i+j}{i}\binom{n-t-i-j-2}{k-1}\sum_{a_r}C_D(i,k,a_r)\cdot C_U(j,n-t-i-j-k-1,a_r) \end{aligned} $$ 红色表示染红部分的方案数，绿色表示染绿部分的方案数，蓝色表示“交织”的方案数。枚举 $D$ 会比枚举 $a_{r+1}$ 稍微方便一点。$C_D$ 和 $C_U$ 主要是为了突出有关变量仅有三个（预处理即可）。
对于 $a_{r+1}=a_r$，枚举 $l=r-t-1$ 以及 $a_r$，方案数为： $$ \begin{aligned} &\sum_i\sum_k\textcolor{red}{\binom{a_r-L-1}{i}\binom{m-a_r}{n-t-l-k-2}}\textcolor{green}{\binom{R-a_r-1}{l-i}\binom{a_r-1}{k}}\textcolor{blue}{\binom{l}{i}\binom{n-t-l-2}{k}}\\ ={}&\left[\sum_i\binom{a_r-L-1}{i}\binom{R-a_r-1}{l-i}\binom{l}{i}\right]\left[\sum_k\binom{a_r-1}{k}\binom{m-a_r}{n-t-l-k-2}\binom{n-t-l-2}{k}\right]\\ ={}&C_L(l,a_r)\cdot C_R(n-t-l-2,a_r) \end{aligned} $$ 这里明确一下组合意义：
- $C_D(i,j,a)$ 表示 $a_r=a$，要安排 $<a_r$ 的数，交叉前个数为 $i$，交叉后个数为 $j$ 的方案数。
- $C_U(i,j,a)$ 表示 $a_r=a$，要安排 $>a_r$ 的数，交叉前个数为 $i$，交叉后个数为 $j$ 的方案数。
- $C_L(i,a)$ 表示 $a_r=a$，要安排 $r$ 之前的数共 $i$ 个的方案数（不考虑交叉条件）。
- $C_R(i,a)$ 表示 $a_r=a$，要安排 $r$ 之后的数共 $i$ 个的方案数（不考虑交叉条件）。
$r=n$ 的情况可以顺便计入。总体来说，计算方案数为 $\mathrm{O}(n^3m)$，实际表现比 dp 还快。下面是计算得分和，思路与求方案数类似。
Step 4
以下 $a_r=a_{r+1}$ 情况部分时间复杂度都是 $\mathrm{O}(n^2m)$，一般情况部分则是 $\mathrm{O}(n^3m)$。代码中的顺序和分析的顺序是一样的。
交叉前下部
首先，不考虑交叉后部分与交叉前上部数值的安排，它们充其量就是外面乘一个系数。枚举交叉前 $<a_r$ 的数个数 $i$，交叉前 $>a_r$ 的数个数 $j$，以及 $D$，该部分得分为： $$ \begin{aligned} &\sum_{p=1}^i\left[\sum_{q=0}^j\binom{p-1+q}{p-1}\binom{i-p+j-q}{i-p}(q+Y)\right]\left[\sum_{a=L+1}^D\binom{a-L-1}{p-1}\binom{D-a-1}{i-p-1}(m-a+1)\right]\\ ={}&\sum_{p=1}^i\left[\binom{i+j}{i+1}p+\binom{i+j}{i}Y\right]\left[\binom{D-L-1}{i-1}(m-L+1)-\binom{D-L}{i}p\right]\\ ={}&\binom{i+j}{i}\binom{D-L-1}{i-1}\left[\frac{ij(m-L+1)}{2}-\frac{(2i+1)j(D-L)}{6}+iY(m-L+1)-\frac{(i+1)Y(D-L)}{2}\right] \end{aligned} $$ 其中 $p$ 枚举交叉前下部的第几个数（称为“它”），$q$ 枚举有交叉前上部有几个数在它前面，$a$ 枚举它的值。第一个等号是利用 Vandermonde 恒等式，第二个等号就是正整数次方求和。记该式为 $(*)$。
接下来再把剩余未确定的部分确定，枚举交叉后 $<a_r$ 的数个数 $k$，最终得分为： $$ \begin{aligned} &\sum_{a_r>D}(*)\binom{R-a_r-1}{j}\binom{D}{k}\binom{m-a_r}{n-t-i-j-k-1}\binom{n-t-i-j-2}{k-1}\\ ={}&(*)\binom{D}{k}\binom{n-t-i-j-2}{k-1}\sum_{a_r>D}C_U(j,n-t-i-j-k-1,a_r)\\ ={}&(*)\binom{D}{k}\binom{n-t-i-j-2}{k-1}C^\prime_U(j,n-t-i-j-k-1,D) \end{aligned} $$ 预处理 $C_U(i,j,*)$ 的后缀和就不用枚举 $a_r$ 了。
交叉前上部
思路是差不多的。先枚举交叉前 $<a_r$ 的数个数 $i$，交叉前 $>a_r$ 的数个数 $j$，以及 $a_r$，该部分得分为： $$ \begin{aligned} &\sum_{p=1}^j\left[\sum_{q=0}^i\binom{p-1+q}{p-1}\binom{j-p+i-q}{j-p}(q+X)\right]\left[\sum_{a=a_r+1}^{R-1}\binom{R-a-1}{p-1}\binom{a-a_r-1}{j-p}a\right]\\ ={}&\sum_{p=1}^j\left[\binom{i+j}{j+1}p+\binom{i+j}{j}X\right]\left[\binom{R-a_r-1}{j}R-\binom{R-a_r}{j+1}p\right]\\ ={}&\binom{i+j}{j}j\left[\binom{R-a_r-1}{j}\left(\frac{i}{2}+X\right)R-\binom{R-a}{j+1}\left(\frac{i(2j+1)}{6}+\frac{(j+1)X}{2}\right)\right] \end{aligned} $$ 抱歉让强迫症难受了，没法化得对称，否则分母上就会有未知数，得乘逆元了 /lb。
剩余未确定的部分的方案数同理，枚举一下 $k$，就不写了，要乘 $C_D$ 等。
另外 $a_{r+1}=a_r$ 和 $r=n$ 的情况的交叉前也可以方便地在这里算掉（反正都枚举 $a_r$ 了）。交叉前下部里就不用算了，会在 $a_i\mapsto m-a_i+1$ 时当成上部算掉。
另一种思路是不推上部，直接推 $a_{r+1}>a_r$ 情况的下部，我没试过，应该也是可以的。
交叉点
枚举交叉前 $<a_r$ 的数个数 $i$，交叉前 $>a_r$ 的数个数 $j$，交叉后 $<a_r$ 的数个数 $k$，最终得分为： $$ \sum_{a_r}C_D(i,k,a_r)\cdot C_U(j,n-t-i-j-k-1,a_r)\cdot\max((Y+j)(m-a_r+1),(X+i)a_r) $$ $a_{r+1}=a_r$ 的部分可能要特殊考虑一下，代码里处理的思路是和交叉前放在一起算，直接乘 $C_R$，就不用枚举 $k$ 了。
交叉后下部
交叉后就无需考虑 $r=n$ 了。先不考虑上部与“交织”的安排。枚举交叉前 $<a_r$ 的数个数 $i$，交叉后 $<a_r$ 的数个数 $k$，以及 $D$，该部分得分为：
$$ \begin{aligned} &\sum_{i\le t,a_i\le L}\sum_{p=a_i+1}^D\binom{D-L-1}{i-1}\binom{D-1}{k-1}p+\sum_{a=L+1}^D\sum_{p=a+1}^D\binom{D-L-2}{i-2}\binom{D-1}{k-1}p\\ =&\binom{D-1}{k-1}\left[\binom{D-L-1}{i-1}\underline{\sum_{i\le t,a_i\le L}\frac{(a_i+1+D)(D-a_i)}{2}}_{f_0(D)}+\binom{D-L-2}{i-2}\underline{\sum_{a=L+1}^D\frac{(a+1+D)(D-a)}{2}}_{f(D)}\right] \end{aligned} $$
其中 $p$ 枚举的是交叉后下部的某个数值。记该式为 $(*)$。划线部分可以预处理。
考虑剩余部分，枚举交叉前 $>a_r$ 的数个数 $j$，最终得分为： $$ (*)\binom{i+j}{i}\binom{n-t-i-j-2}{k-1}C^\prime_U(j,n-t-i-j-k-1,D) $$
交叉后上部
$$ {\underline{a}{f}}{\underline{b}{f}} $$
先枚举交叉前 $>a_r$ 的数个数 $j$，交叉后 $>a_r$ 的数个数 $k$，以及 $a_r$，该部分得分为： $$ \binom{m-a_r-1}{k-1}\underline{\left[\binom{R-a_r-1}{j}\sum_{i\le t,a_i\ge R}\frac{(2m-a_i-a_r+2)(a_i-a_r-1)}{2}+\binom{R-a_r-2}{j-1}\sum_{a=a_r+1}^{R-1}\frac{(2m-a-a_r+2)(a-a_r-1)}{2}\right]}_{F(j,a_r)} $$ 最终得分同理也是要乘 $C_D$ 等，略。
同样要处理一下 $a_{r+1}=a_r$，要做到三次方还得分离一下变量： $$ \begin{align} &\sum_{i,j,k,a_r}\binom{a_r-L-1}{i}\binom{m-a_r-1}{k-1}F(j,a_r)\binom{a_r-1}{n-t-i-j-k-2}\binom{i+j}{j}\binom{n-t-i-j-2}{k}\\ =&\sum_{a_r}\sum_l\left[\sum_i\binom{a_r-L-1}{i}F(l-i,a_r)\binom{l}{i}\right]\left[\sum_k\binom{a_r-1}{n-t-l-k-2}\binom{m-a_r-1}{k-1}\binom{n-t-l-2}{k}\right] \end{align} $$ $l$ 就是 $i+j$ 换元，跟 Step 3 里的 $l$ 是一样的。注意第二个中括号里的不是 $C_R$。
Step 5
说一下优化：我们希望瓶颈部分（四次方的最内层循环）运算次数尽量少，所以可以把只涉及到一部分变量的乘法先预处理掉，把能用分配律的乘法提到外层。
然后就是 $18$ 次一取模优化。
Code
#define ansc ans. first
#define anss ans. second
int calcP() {
int res = 0; CL (tree);
for (int i=1; i<=t; i++)
update(A[i]), res += c[i] ? getsum(A[i] - 1) * A[i] : (i - getsum(A[i])) * (m - A[i] + 1);
return res;
}
pii calcX(int L, int R) {
pii ans (0, 0); CL (cnt);
int pre = calcP(), sumd = 0, sumu = 0;
if (t == n) return {1, pre};
for (int i=1; i<=t; i++) cnt[A[i]] ++;
for (int i=1; i<L; i++) sumd += cnt[i-1] * i, cnt[i] += cnt[i-1];
for (int i=m; i>R; i--) sumu += cnt[i+1] * (m - i + 1), cnt[i] += cnt[i+1];
for (int i=max(0,n-t-m+R); i<=min(L-1,n-t); i++) {
ansc = (ansc + 1ll * C[L-1][i] * C[m-R][n-t-i] % MOD * C[n-t][i]) % MOD;
if (i) anss = (anss + 1ll * C[L-2][i-1] * C[m-R][n-t-i] % MOD * C[n-t][i] % MOD * sumd) % MOD;
if (n - t - i) anss = (anss + 1ll * C[L-1][i] * C[m-R-1][n-t-i-1] % MOD * C[n-t][i] % MOD * sumu) % MOD;
} anss = (anss + 1ll * ansc * pre) % MOD;
return ans;
}
pii calcI(int L, int R, bool flag) {
pii ans (0, 0); CL (CD), CL (CU), CL (CUS), CL (CR);
for (int k=0; k<n-t; k++)
for (int a=L+1; a<=m; a++)
CD[0][k][a] = C[L][k];
for (int i=1; i<n-t; i++)
for (int k=0; k<n-t-i; k++)
for (int a=L+i+1; a<=m; a++)
CD[i][k][a] = (CD[i][k][a-1] + 1ll * C[a-L-2][i-1] * C[a-1][k]) % MOD;
for (int j=0; j<n-t; j++)
for (int k=0; k<n-t-j; k++)
for (int a=R-j-1; a>0; a--)
CU[j][k][a] = 1ll * C[R-a-1][j] * C[m-a][k] % MOD,
CUS[j][k][a] = P(CUS[j][k][a+1], CU[j][k][a+1]);
for (int l=0; l<n-t; l++)
for (int a=1; a<=m; a++)
for (int k=0; k<=l; k++)
CR[l][a] = (CR[l][a] + 1ll * C[a-1][k] * C[m-a][l-k] % MOD * C[l][k]) % MOD;
for (int i=0; i<n-t-1; i++)
for (int j=0; j<n-t-i-1; j++)
for (int k=1; k<n-t-i-j; k++) {
ull res = 0;
for (int a=L+i+1, _=0; a<=R-j-1; a++) {
ADD(1ll * CD[i][k][a] * CU[j][n-t-i-j-k-1][a]);
} res %= MOD;
ansc = (ansc + 1ll * C[i+j][i] * C[n-t-i-j-2][k-1] % MOD * res) % MOD;
}
if (flag) for (int l=0; l<n-t; l++)
for (int a=L+1; a<=R-1; a++) {
int CL = 0;
for (int i=0; i<=l; i++)
CL = (CL + 1ll * C[a-L-1][i] * C[R-a-1][l-i] % MOD * C[l][i]) % MOD;
ansc = (ansc + 1ll * CL * (l < n - t - 1 ? CR[n-t-l-2][a] : 1)) % MOD;
}
for (int i=1; i<n-t-1; i++)
for (int j=0; j<n-t-i-1; j++) {
for (int a=L+i; a<=R-j-2; a++)
F[a] = (i3 * j * (3 * i * (m - L + 1) - (2 * i + 1) * (a - L)) + Y * (2 * i * (m - L + 1) - (i + 1) * (a - L))) % MOD * i2 % MOD * C[i+j][i] % MOD * C[a-L-1][i-1] % MOD;
for (int k=1; k<n-t-i-j; k++) {
ull res = 0;
for (int a=L+i, _=0; a<=R-j-2; a++) {
ADD(1ll * C[a][k] * CUS[j][n-t-i-j-k-1][a] % MOD * F[a]);
} res %= MOD;
anss = (anss + 1ll * C[n-t-i-j-2][k-1] * res) % MOD;
}
}
for (int i=0; i<n-t; i++)
for (int j=0; j<n-t-i; j++) {
for (int a=L+i+1; a<=R-j-1; a++)
F[a] = (1ll * C[R-a-1][j] * R * (i + 2 * X) + i3 * (MOD - C[R-a][j+1]) % MOD * (i * (2 * j + 1) + 3 * (j + 1) * X)) * j % MOD * i2 % MOD * C[i+j][j] % MOD;
if (j)
if (i + j < n - t - 1) for (int k=0; k<n-t-i-j-1; k++) {
ull res = 0;
for (int a=L+i+1, _=0; a<=R-j-1; a++) {
ADD(1ll * C[m-a][k] * CD[i][n-t-i-j-k-1][a] % MOD * F[a]);
} res %= MOD;
anss = (anss + 1ll * C[n-t-i-j-2][k] * res) % MOD;
} else for (int a=L+i+1; a<=R-j-1; a++)
anss = (anss + 1ll * CD[i][0][a] * F[a]) % MOD;
if (i + j < n - t - 1) for (int a=L+i+1; a<=R-j-1; a++)
anss = (anss + 1ll * (F[a] + 1ll * (X + i) * a * C[R-a-1][j] % MOD * C[i+j][i]) % MOD * C[a-L-1][i] % MOD * CR[n-t-i-j-2][a]) % MOD;
}
for (int i=0; i<n-t; i++)
for (int j=0; j<n-t-i; j++)
for (int k=0; k<n-t-i-j; k++) {
ull res = 0;
for (int a=L+i+1, wr=(Y+j)*(m-a+1), wg=(X+i)*a; a<=R-j-1; a++, wr-=Y+j, wg+=X+i) {
res += 1ll * CD[i][k][a] * CU[j][n-t-i-j-k-1][a] % MOD * max(wr, wg);
} res %= MOD;
if (i + j == n - t - 1 && flag) anss = (anss + 1ll * C[i+j][i] * res) % MOD;
else if (k) anss = (anss + 1ll * C[i+j][i] * C[n-t-i-j-2][k-1] % MOD * res) % MOD;
}
CL (f0), CL (f);
for (int a=L; a<=R-2; a++) {
for (int i=1; i<=t; i++) if (A[i] <= L)
f0[a] += (A[i] + 1 + a) * (a - A[i]) >> 1;
for (int i=L+1; i<=a; i++)
f[a] += (i + 1 + a) * (a - i) >> 1;
}
for (int i=0; i<n-t-1; i++)
for (int k=1; k<n-t-i; k++) {
if (! i) {
F[L] = L ? 1ll * C[L-1][k-1] * f0[L] % MOD : 0;
for (int a=L+1; a<=R-2; a++) F[a] = 0;
} else for (int a=L+i; a<=R-2; a++)
F[a] = (1ll * C[a-L-1][i-1] * f0[a] + (i > 1 ? 1ll * C[a-L-2][i-2] * f[a] : 0)) % MOD * C[a-1][k-1] % MOD;
for (int j=0; j<n-t-i-k; j++) {
ull res = 0;
for (int a=L+i, _=0; a<=R-j-2; a++) {
ADD(1ll * CUS[j][n-t-i-j-k-1][a] * F[a]);
} res %= MOD;
anss = (anss + 1ll * C[i+j][i] * C[n-t-i-j-2][k-1] % MOD * res) % MOD;
}
}
CL (f0), CL (f), CL (_F);
for (int a=L+1; a<=R-1; a++) {
for (int i=1; i<=t; i++) if (A[i] >= R)
f0[a] += (2 * (m + 1) - A[i] - a) * (A[i] - a - 1) >> 1;
for (int i=a+1; i<=R-1; i++)
f[a] += (2 * (m + 1) - i - a) * (i - a - 1) >> 1;
}
for (int j=0; j<n-t-1; j++) {
for (int a=L+1; a<=R-j-1; a++)
_F[a][j] = (1ll * C[R-a-1][j] * f0[a] + (j ? 1ll * C[R-a-2][j-1] * f[a] : 0)) % MOD;
for (int k=1; k<n-t-j-1; k++) {
for (int a=L+1; a<=R-j-1; a++)
F[a] = a < m ? 1ll * C[m-a-1][k-1] * _F[a][j] % MOD : 0;
for (int i=0; i<n-t-j-k-1; i++) {
ull res = 0;
for (int a=L+i+1, _=0; a<=R-j-1; a++) {
ADD(1ll * CD[i][n-t-i-j-k-1][a] * F[a]);
} res %= MOD;
anss = (anss + 1ll * C[i+j][j] * C[n-t-i-j-2][k] % MOD * res) % MOD;
}
}
}
for (int l=0; l<n-t-1; l++)
for (int a=L+1; a<=min(R-1,m-1); a++) {
int res1 = 0, res2 = 0;
for (int i=max(0,a-R+l+1); i<=min(l,a-L-1); i++)
res1 = (res1 + 1ll * C[a-L-1][i] * C[l][i] % MOD * _F[a][l-i]) % MOD;
for (int k=1; k<n-t-l-1; k++)
res2 = (res2 + 1ll * C[n-t-l-2][k] * C[a-1][n-t-l-k-2] % MOD * C[m-a-1][k-1]) % MOD;
anss = (anss + 1ll * res1 * res2) % MOD;
}
return ans;
}
pii calcF(int L, int R) {
pii ans (0, 0);
ans += calcI(L, R, 1);
for (int i=1; i<=t; i++) A[i] = m - A[i] + 1; swap(X, Y);
ans += calcI(m - R + 1, m - L + 1, 0);
for (int i=1; i<=t; i++) A[i] = m - A[i] + 1; swap(X, Y);
anss = (anss + 1ll * ansc * calcP()) % MOD;
return ans;
}
pii calcN() {
pii ans (0, 0);
c[t] = 1, Y ++, ans += calcF(L, A[t]), Y --;
c[t] = A[t] * X > (m - A[t] + 1) * Y, t ++;
for (int i=1; i<=L; i++)
A[t] = i, c[t] = 1, ans += calcX(i, A[t-1]);
c[t] = c[t-1] ^ 1, ans += calcX(A[t-1], A[t] = A[t-1]);
for (int i=R; i<=m; i++)
A[t] = i, c[t] = 0, ans += calcX(A[t-1], i);
t --;
c[t] = 0, X ++, ans += calcF(A[t], R), X --;
return ans;
}
int main() {
for (int i=0; i<=200; i++) {
C[i][0] = 1;
for (int j=1; j<=min(i,50); j++)
C[i][j] = P(C[i-1][j-1], C[i-1][j]);
}
cin >> T;
while (T --) {
cin >> n >> m >> t, L = X = Y = 0, R = m + 1;
for (int i=1; i<=t; i++) scanf ("%d", &A[i]);
for (int i=2; i<=t; i++)
if (L < R)
if (L < A[i] && A[i] < A[i-1])
R = A[i-1], c[i-1] = 1, Y ++;
else if (A[i-1] < A[i] && A[i] < R)
L = A[i-1], c[i-1] = 0, X ++;
else if (A[i] == A[i-1])
L = R = A[i], c[i-1] = 0, c[i] = 1;
else {
c[i-1] = A[i-1] * X > (m - A[i-1] + 1) * Y;
if (A[i] < A[i-1]) L = A[i-1], R = A[i], c[i] = 1;
else L = A[i], R = A[i-1], c[i] = 0;
}
else if (A[i] > L) L = A[i], c[i] = 0;
else if (A[i] < R) R = A[i], c[i] = 1;
else { ans = {0, 0}; goto O; }
if (L < R && t == n) c[n] = A[n] * X > (m - A[n] + 1) * Y, L = R = 0;
ans = L >= R ? calcX(R, L) : calcN();
O : printf ("%d %d\n", ansc, anss);
}
}