P7716 「EZEC-10」Covering

给你一个 $n\times m$ 的棋盘和 $k$ 张 $1\times 2$ 的纸片，编号 $1$ 到 $k$。 你可以任意选择数量在 $[l,r]$ 内的纸片，并按照编号从小到大的顺序，依次横放或竖放在棋盘上。 **注意：后放的纸片会覆盖在先放的纸片上。** 给定最终棋盘中每个格子上的纸片编号，求满足条件的不同方案数，并对 $10^9+7$ 取模。 **两种方案相同，当且仅当两方案选择的纸片数量、纸片编号及每张纸片的摆放位置均相同。**

无

无

**【样例 1 解释】** 不难发现只能取编号为 $1,2,3$ 的纸片，此时共有 $2$ 种方案： $1:(1,1)\to (1,2)$，$2:(1,2)\to (2,2)$，$3:(2,1)\to (2,2)$； $1:(1,1)\to (2,1)$，$2:(1,2)\to (2,2)$，$3:(2,1)\to (2,2)$。 **【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1（5 points）：$r=1$。 - Subtask 2（10 points）：$n,m,k\le 5$。 - Subtask 3（15 points）：$l=k$。 - Subtask 4（20 points）：$n\times m\le 10^3$。 - Subtask 5（50 points）：无特殊限制。 对于 $100\%$ 的数据，$1\le T\le 10$，$2\le n,m,k\le 10^3$，$1\le l\le r\le k$。