#P18739. [正睿NOI2021训练] 第一题
[正睿NOI2021训练] 第一题
第一题
在一个 的网格中选择若干格子涂黑,满足:
- 所有黑格四连通。
- 不存在四个黑格组成 的正方形。
- 不存在四个黑格组成 T 字形,即一个黑格及其三个上下左右相邻格子不能同时为黑色。
已知第一行恰有 个黑格,第二行恰有 个黑格。求不同涂色方案数,对 取模。网格的位置固定,旋转或反射后的不同格子集合仍是不同方案。
输入格式
一行三个整数 。
输出格式
一个整数,表示方案数模 的结果。
数据范围
,,。允许其中一行没有黑格。
样例 1
输入
5 2 4
输出
4
样例 2
输入
3 0 1
输出
3
第二个样例中,只有第二行的一个格子涂黑,共有三个可选位置。