#P17932. Akari Counting
Akari Counting
Akari Counting
有一个 行 列的网格。第 行第 列记为 ,行从上到下、列从左到右编号。
当且仅当 且 时,格子 为黑色;其他格子均为白色。
可以在若干白格中各放置一盏灯。位于 的灯照亮与它同行或同列、且中间没有黑格阻挡的所有白格,包括它所在的格子。
一个放灯方案合法,当且仅当:
- 所有白格都被至少一盏灯照亮;
- 任意一盏灯所在的格子都不能被其他灯照亮。
求合法方案数对 取模的结果。
输入格式
H W A B C D
输出格式
输出一个整数,表示答案。
数据范围
,。
保证 且 。所有输入均为整数。
样例 1
输入:
3 3 2 2 2 2
输出:
7
样例 2
输入:
2 3 1 1 1 2
输出:
3
样例 3
输入:
500000 500000 100000 200000 100000 250000
输出:
360665510