A16801 · 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$ 取模。

输入输出样例

输入 #1

输出 #1

A16801 | Control Car (Easy Version)

题目描述

输入格式

输出格式

输入输出样例

A16801 | $Control Car (Easy Version)$