luogu#P10681. [COTS/CETS 2024] 奇偶矩阵 Tablica

    ID: 14619 远端评测题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>动态规划,dp递推2024O2优化CEOI(中欧)生成函数,GF线性递推COCI(克罗地亚)

[COTS/CETS 2024] 奇偶矩阵 Tablica

题目背景

译自 Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D1T2。1s,1G\texttt{1s,1G}。

题目描述

考虑只包含 0011N×MN\times M 矩阵 AA

我们称满足以下条件的矩阵是好的:

  • 1iN\forall 1\le i\le Nj=1MAi,j{1,2}\displaystyle \sum_{j=1}^M A_{i,j}\in \{1,2\}
  • 1jM\forall 1\le j\le Mi=1NAi,j{1,2}\displaystyle \sum_{i=1}^N A_{i,j}\in \{1,2\}

求出 NNMM 列的好的矩阵的数量,对 (109+7)(10^9+7) 取模。

输入格式

输入共一行两个正整数,即 N,MN,M

输出格式

输出一行一个整数,表示答案对 (109+7)(10^9+7) 取模后的结果。

2 2
7
3 3
102
15 20
415131258

提示

样例解释

样例 11 解释如图所示。

数据范围

对于 100%100\% 的数据,1N,M30001\le N,M\le 3\, 000

子任务编号 分值 约束
11 1010 N,M6N, M \leq 6
22 1818 N,M50N, M \leq 50
33 3131 N,M200N, M \leq 200
44 4141 无额外约束