题目背景
译自 Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D1T2。1s,1G。
题目描述
考虑只包含 0 和 1 的 N×M 矩阵 A。
我们称满足以下条件的矩阵是好的:
- ∀1≤i≤N,j=1∑MAi,j∈{1,2};
- ∀1≤j≤M,i=1∑NAi,j∈{1,2}。
求出 N 行 M 列的好的矩阵的数量,对 (109+7) 取模。
输入格式
输入共一行两个正整数,即 N,M。
输出格式
输出一行一个整数,表示答案对 (109+7) 取模后的结果。
2 2
7
3 3
102
15 20
415131258
提示
样例解释
样例 1 解释如图所示。
数据范围
对于 100% 的数据,1≤N,M≤3000。
子任务编号 |
分值 |
约束 |
1 |
10 |
N,M≤6 |
2 |
18 |
N,M≤50 |
3 |
31 |
N,M≤200 |
4 |
41 |
无额外约束 |