CF2180F1 Control Car (Easy Version)

这道题有两个版本，区别在于变量范围、时间和内存限制。只有同时解决了两个版本，你才能 hack 其他人的代码。请注意，困难版本的正确解法不一定适用于简单版本。 我们有一辆“控制车”，它的行为和一个随机变量类似。正如随机变量既不真正随机也不真正可变，我们的控制车既不是一辆车，也不可控！ 不管怎样，给定一个 $n \times m$ 的网格，由 $n+1$ 条水平线和 $m+1$ 条竖直线相交形成。网格共有 $(n+1)(m+1)$ 个交点，这些交点围成了所有的单元格。 一次“定向”指的是给每一个交点分配一个四个基本方向（上、下、左、右）之一。因此，一共有 $4^{(n+1)(m+1)}$ 种不同的定向方式。 对于每一种定向方式，执行以下过程： 1. 对于每个网格点，我们按其定向在该点处画出长度为 1 单位的“墙”。墙可能会重叠，也可能会超出网格边界。 2. 将控制车放在左上角的单元格 $(1,1)$。然后，遵循如下规则不断移动，直到停止为止： - 如果控制车可以向下移动（即下方没有墙阻挡），则它由于重力向下移动。 - 如果不能向下移动但可以向右移动（即右边没有墙阻挡），则向右移动。 - 如果控制车离开了网格或无法前进，就停止。 3. 若控制车最终停在网格内部，则该定向方式是“合法”的。 请你计算有多少种“合法”的定向方式。由于答案可能很大，请输出其对 $10^9+7$ 取模的结果。

本题包含多组测试数据。第一行输入测试用例数 $t$（$1 \le t \le 10^4$）。 每组测试数据一行，包含两个整数 $n$ 和 $m$（$1 \le n, m \le 5000$），表示网格的大小。

每组测试数据输出一行，表示合法定向方式的数量，对 $10^9+7$ 取模。

在第一个测试用例中，若一个定向为合法，则需要至少用左下角或右下角的墙覆盖正方形底部边界，同时需要用右上角或右下角的墙覆盖右侧边界。如果这些条件都满足，则该定向合法。 现在，如果右上角点向下，左下角点向右，那么左上角和右下角的点可以朝任意方向定向。这样就有 $16$ 种合法定向。  第一类合法定向的例子。如果右上角或左下角的方向不同，那么右下角必须覆盖对应的边界。这种情况下，每次只能有一个点方向不同，共有 $2 \cdot 3 \cdot 4 = 24$ 种定向。  第二类合法定向的例子。因此，最终答案为 $16 + 24 = 40$。   两个非法定向的例子。 [可视化工具链接](https://codeforces.com/assets/contests/2180/F_eegai9Doo0heequiev6e.html) 由 ChatGPT 5 翻译