CF2180F2.Control Car (Hard Version)

The two versions differ in the limits, including variable bounds, as well as time and memory constraints. You can hack only if you solve both versions of this problem. Note that a correct solution for the hard version is not necessarily a valid solution for the easy version.

We have a control car that behaves like a random variable. As a random variable is neither truly random nor truly variable, our control car is neither a car nor controllable!

Anyhow, we are given a grid of size $n \times m$ formed by the intersections of $n+1$ horizontal lines and $m+1$ vertical lines. The grid contains $(n+1)(m+1)$ intersection points, which are the corners surrounding the cells.

An orientation is an assignment of one of the four cardinal directions (up, down, left, right) to each of these $(n+1)(m+1)$ intersection points. Therefore, there are $4^{(n+1)(m+1)}$ possible orientations.

Consider the process below for an orientation:

1. For each point in the grid, we draw a wall extending in the direction it is oriented with length one unit. Walls may overlap or extend beyond the grid boundary.
2. Place the control car at the top-left corner cell $(1, 1)$. Then, as long as the car has not stopped, it moves according to these rules:
   • If it can move down (i.e., no wall blocks the path to the cell directly below), it moves down because of gravity.
   • If it cannot move down but can move right (i.e., no wall blocks the path to the cell directly to its right), it moves right.
   • If the car exits the grid or cannot move, it stops.
3. The orientation is valid if the control car stops inside the grid.

Count the number of valid orientations. As the number of valid orientations can be huge, print the answer modulo $10^9+7$.

两个版本在限制条件上有所不同，包括变量的取值范围，以及时间和内存限制。只有当你同时解决了本题的两个版本时，才允许进行 Hack。注意：一个适用于困难版本的正确解法，未必适用于简单版本。

我们有一辆“控制小车”，其行为类似于一个随机变量。而由于随机变量既非真正随机，也非真正可变，我们的这辆“控制小车”既不是一辆车，也无法被真正控制！

无论如何，我们给定一个由 $n+1$ 条水平线与 $m+1$ 条垂直线相交构成的 $n \times m$ 网格。该网格包含 $(n+1)(m+1)$ 个交点，这些交点即为围成各个单元格的角点。

一种朝向配置（orientation） 是将四个基本方向（上、下、左、右）之一分配给上述 $(n+1)(m+1)$ 个交点中的每一个。因此，共有 $4^{(n+1)(m+1)}$ 种可能的朝向配置。

对任一朝向配置，考虑如下过程：

1. 对于网格中的每个交点，沿其指定方向绘制一堵长度为 1 单位的墙。墙可以重叠，也可以延伸出网格边界。
2. 将控制小车置于左上角单元格 $(1, 1)$ 中。随后，只要小车尚未停止，它就按以下规则移动：
   • 若它能向下移动（即：正下方单元格的路径未被墙阻挡），则因重力作用向下移动；
   • 若它不能向下移动，但能向右移动（即：正右方单元格的路径未被墙阻挡），则向右移动；
   • 若小车移出网格边界，或无法继续移动，则停止。
3. 若控制小车最终停在网格内部（即停在某个单元格内，而非网格外），则称该朝向配置是有效的（valid）。

请计算有效朝向配置的总数。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le \mathbf{50}$, $1 \le m \le \mathbf{10^{15}}$), the sizes of the grid.

The sum of $n$ over all test cases is at most $\mathbf{50}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 50$）。随后是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le \mathbf{50}$，$1 \le m \le \mathbf{10^{15}}$），表示网格的尺寸。

所有测试用例中 $n$ 的总和不超过 $\mathbf{50}$。

For each test case, output the number of valid orientations modulo $10^9+7$.

对于每个测试用例，输出有效朝向的数量对 $10^9+7$ 取模的结果。

In the first test case, for an orientation to be valid, we need at least one of the lower-left or lower-right walls to cover the bottom border of the square. We also need at least one of the upper-right or lower-right walls to cover the right border. If both of these conditions hold, then the orientation is valid.

Now, if the upper-right corner points downward and the lower-left corner points to the right, then the upper-left and lower-right corners can point in arbitrary directions. Hence, there are $16$ valid orientations of this type.

Example of a valid orientation of the first type.

If one of the upper-right or lower-left corners points in a different direction, the lower-right corner must cover the corresponding border. Therefore, only one of them can point in a different direction. In total, there are $2 \cdot 3 \cdot 4 = 24$ valid orientations of this type.

Example of a valid orientation of the second type.

Thus, the final answer is $16 + 24 = 40$.

Examples of two invalid orientations.

Link to the visualizer

在第一个测试用例中，一个朝向要有效，需满足以下条件：左下角或右下角的墙壁中至少有一个覆盖正方形的底边；右上角或右下角的墙壁中至少有一个覆盖正方形的右边。若这两个条件同时成立，则该朝向是有效的。

现在，若右上角指向下方、左下角指向右方，则左上角和右下角可任意指向。因此，此类有效朝向共有 $16$ 种。

第一类有效朝向的示例。

若右上角或左下角中恰好有一个指向了其他方向，则右下角必须覆盖对应的边。因此，仅允许其中一者指向不同方向。此类有效朝向总数为 $2 \cdot 3 \cdot 4 = 24$ 种。

第二类有效朝向的示例。

因此，最终答案为 $16 + 24 = 40$。

两种无效朝向的示例。

可视化工具链接