#P15899. [Roi2021 Team]Yurik and Woodwork Lesson / Yurik 的木工课
[Roi2021 Team]Yurik and Woodwork Lesson / Yurik 的木工课
题目描述
今天 Yurik 很早起床,因为第一节课是他最喜欢的木工课。但他失望地发现,今天要考试。
上课开始时,老师给每个学生发了一块大小为 的木板。木板被铅笔线分成 行 列,共 个 的小方格。
考试要求学生用线锯切掉一些格子,使剩余木板是“好的”。一块木板称为好的,当且仅当满足以下五个条件:
- 左上角格子没有被切掉;
- 右下角格子没有被切掉;
- 剩余格子构成连通区域。也就是说,可以从任意剩余格子通过上下左右相邻移动到达任意另一个剩余格子;
- 对每一行,未被切掉的格子形成一个连续的水平区间;
- 对每一列,未被切掉的格子形成一个连续的竖直区间。
不满足上述至少一个条件的木板称为“坏的”。

此处给出了 木板中若干好的与坏的示例,左上角和右下角格子用灰色标出。
Yurik 不想认真考试,而是想知道:从原始 木板中切掉若干个格子(可以一个也不切)后,一共能得到多少种不同的好木板?如果切掉的格子集合不同,则认为两种木板不同。
请你计算答案。
输入格式
输入一行两个整数 ,表示原始木板尺寸。
输出格式
输出一个整数,表示不同好木板的数量。由于答案可能很大,请输出其对 取模后的结果。
数据范围
。
样例
输入:
2 2
输出:
3
输入:
2 4
输出:
10
输入:
100 100
输出:
818380736
样例说明

此处给出了 和 木板所有好木板的示意图。