Потрошение вывески

시간 제한1.5초메모리 제한1024 MB

요약

n x m 격자를 매 단계에서 하나의 행이나 열을 골라 재귀적으로 분할하는 방법의 수를 세되, 분할의 행/열 구분을 서로 다른 것으로 보고 10^9+7로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론, 재귀
정답자: 아직 제출이 없습니다

문제

Хэллоуин --- очень популярное событие, в котором участвуют взрослые и дети всех возрастов. Разумеется, каждому владельцу магазина на главной улице города хочется чем-то выделиться, чтобы привлечь к себе как можно больше покупателей.

Некоторые пытаются выставить у себя на витринах самые красивые или, наоброт, жуткие тыквы, а некоторые пытаются креативно оформить рекламные вывески. Владелец <<Лавки Джека-Потрошителя>> решил <<распотрошить>> свою вывеску, чтобы она стала самой оригинальной на всей улице.

Вывеска представляет из себя таблицу размера $n \times m$ , в каждой клетке которой может быть размещена ровно одна буква. Сама рекламная надпись состоит в точности из $n \cdot m$ букв. Распотрошить вывеску можно либо по любой строке, либо по любому столбцу. Потрошение по строке номер $i$ , например, выглядит следующим образом:

Верхняя часть таблицы, состоящая из первых $i - 1$ строк, рекурсивно потрошится, и в нее записываются буквы с $1$ -й по $(i - 1) \cdot m$ -ю;
Строка номер $i$ обводится, и на ней обозначается направление слева-направо. В этом направлении в ней выписываются буквы с $(i - 1) \cdot m + 1$ -й по $i \cdot m$ -ю;
Аналогично верхней части, нижняя часть таблицы (строчки с $i + 1$ -й по $n$ -ю) тоже рекурсивно потрошится, и в ней записываются оставшиеся буквы.

Симметричным образом происходит потрошение по столбцу --- на нем указывается направление сверху-вниз, в котором выписываются соответствующие буквы, а левая и правая части, если не пусты, рекурсивно потрошатся.

Владельцу лавки стало интересно, сколько есть различных способов распотрошить вывеску. Два способа считаются различными, если хотя бы одна ячейка таблицы, принадлежащая какой-то выделенной строке в одном из способов, принадлежит выделенному столбцу в другом. Обратите внимание, что выделить в таблице $1 \times 1$ строку и выделить столбец --- разные способы!

Поскольку число способов может быть достаточно большим, выведите его по модулю $10^9 + 7$ .

입력

В единственной строке через пробел дано два целых числа $n$ и $m$ ( $1 \leqslant n, m \leqslant 200$ ).

출력

Выведите единственное целое число --- количество способов распотрошить вывеску по модулю $10^9 + 7$ .

힌트

Все возможные потрошения во втором примере:

예제3

예제 1
입력
```
1 1
```
예상 출력
```
2
```
예제 2
입력
```
2 2
```
예상 출력
```
14
```
예제 3
입력
```
3 2
```
예상 출력
```
48
```