考虑将问题抽象成：左上角为 \((0,0)\) 右下角为 \((n,m)\) 的网格图，求所有满足至少有一条 只向下或向右走的路径 经过点集内所有点的的不同的点集大小之和。
那么显然拐点有两类，一个是右转的一个是向下转的。
图片来自于洛谷题解区 zltqwq
然后很显然，当我们列出 所有向下转的拐点 时，路径就被唯一确定了。
考虑选择拐点的方案数。
设这样的拐点有 \(i\) 个，那么显然所有前面的拐点都严格小于后面的拐点，直接 横坐标范围 \([1,m]\) 内任选，纵坐标范围 \([0,n-1]\) 内任选即可。
方案为 \(\binom{n}{i}\binom{m}{i}\)。
路径上还有 \(s = n + m - i - 1\) 个点，随便选不选。
总贡献为 \(\Sigma_{j=0}^s \binom{s}{j}{i + 2 + j} = (i +2) 2 ^ s + s2^{s-1}\)。
Tips：
单调移动的题可以抽象到网格图上处理，不过确定路径需要仔细考虑。