打表
容易发现 $n,m$ 没有什么区别，即 $n$ 行 $m$ 列的棋盘等价于 $m$ 行 $n$ 列的棋盘。
观察数据范围，可以发现 $n\leq8$，而 $m\leq10^6$。
因此可以考虑打表，然后找一下规律。
打出来表得到：
1
2
3
4
5
6
7
8
9
10
11
int f[9][9]={
{0,0,0,0,0,0,0,0,0},
{0,2,4,8,16,32,64,128,256},
{0,4,12,36,108,324,972,2916,8748},
{0,8,36,112,336,1008,3024,9072,27216},
{0,16,108,336,912,2688,8064,24192,72576},
{0,32,324,1008,2688,7136,21312,63936,191808},
{0,64,972,3024,8064,21312,56768,170112,510336},
{0,128,2916,9072,24192,63936,170112,453504,1360128},
{0,256,8748,27216,72576,191808,510336,1360128,3626752}
};
记 $\textit{ans}_{n,m}$ 为 $n$ 行 $m$ 列的棋盘的答案，钦定 $n\leq m$，则有：
- $n=1$ 时，$\textit{ans}_{n,m}=2^m$。
- $n>1$ 时，\(\textit{ans}_{n,m}=3\cdot\textit{ans}_{n,m-1}\)。
于是就可以愉快地 AC 了。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=8,M=1e6,P=1e9+7;
int n,m;
int f[N+1][N+1]={
{0,0,0,0,0,0,0,0,0},
{0,2,4,8,16,32,64,128,256},
{0,4,12,36,108,324,972,2916,8748},
{0,8,36,112,336,1008,3024,9072,27216},
{0,16,108,336,912,2688,8064,24192,72576},
{0,32,324,1008,2688,7136,21312,63936,191808},
{0,64,972,3024,8064,21312,56768,170112,510336},
{0,128,2916,9072,24192,63936,170112,453504,1360128},
{0,256,8748,27216,72576,191808,510336,1360128,3626752}
};
int qpow(int base,int n){
int ans=1;
while(n){
if(n&1){
ans=1ll*ans*base%P;
}
base=1ll*base*base%P;
n>>=1;
}
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
if(n>m){
swap(n,m);
}
if(n==1){
cout<<qpow(2,m)<<'\n';
}else if(m-1<=N){
cout<<f[n][m]<<'\n';
}else{
int ans;
if(n!=8){
ans=f[n][n+1];
}else{
ans=10879488;
}
for(int i=1;i<=m-n-1;i++){
ans=3ll*ans%P;
}
cout<<ans<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
