CF300D Painting Square

题目描述

熊 Vasily 有一张大的正方形白色桌子，这张桌子由 $n$ 行 $n$ 列组成。桌子的周围有一圈黑色边框。

如上图，$n=5$ 时初始桌子的例子。 Vasily 熊想要用恰好 $k$ 次操作来给这张正方形桌子着色。每次操作包含以下顺序的动作：

1. 熊从桌子内部任选一个正方形区域。这个正方形的边界部分必须已经被涂成黑色，并且正方形内部不能包含黑色单元格。正方形的边长不得小于 $2$。
2. 熊从选中的正方形区域内选择一个行号和一个列号。随后，他将正方形区域内该行和该列的所有单元格涂黑。此后，由正方形的边界和刚才被涂黑的单元格组成的矩形，必须都为面积非零的正方形。

如上图，$n=7$ 且 $k=2$ 时的一个合法涂色示例。 熊已经知道 $n$ 和 $k$ 的值。请你帮助他计算——使用恰好 $k$ 次操作将该桌子涂色的方法总数有多少种。若最终的桌面上，至少有一格不同，则两种涂色方式被认为是不同的。由于答案可能非常大，请你将答案对 $7340033$ 取模后输出。

输入格式

第一行包含整数 $q$（$1 \leq q \leq 10^5$），表示数据组数。

接下来的 $q$ 行，每行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^9, 0 \leq k \leq 1000$），分别表示初始桌子的大小和本次测试的操作次数。

输出格式

对于每组输入数据，输出一个答案，即本组的方案数，对 $7340033$ 取模。按输入顺序输出每组答案。

输入输出样例 #1

输入 #1

8
1 0
1 1
3 0
3 1
2 0
2 1
3 2
7 2

输出 #1

1
0
1
1
1
0
0
4

说明/提示

对于 $n=7$ 且 $k=2$ 的测试，其所有可能的涂色方式如下图所示：

由 ChatGPT 5 翻译