Matching Colors
Есенен Турнир по Програмиране, 2020
Time Limit: 0.5s, Memory Limit: 256MiB
Ели има кариран лист хартия с N реда и M колони. Момичето иска да запълни всяко от квадратчетата с червено или синьо. Тя държи, обаче, за всяко квадратче с даден цвят, да има поне още едно със същия цвят в същия ред или същата колона ("за да не е самотно").

За всяко квадратче е достатъчно да има "двойник по цвят" в същия ред ИЛИ същата колона – но не задължително и в двете (макар и това да е позволено). Също така е позволено да има повече от една клетка със същия цвят в същия ред или колона – например цяла колона запълнена с червено е окей. Не е нужно всеки от цветовете да се среща – така, например, целият лист оцветен в синьо би могло да бъде валидно запълване.

Момичето се чуди по колко различни начина може да бъде запълнен листът? Две запълвания считаме за различни, ако има клетка, която е оцветена в червено при едното от тях, но в синьо при другото.
Вход
На единствен ред на стандартния вход ще бъдат зададени целите числа N и M – съответно броя редове и колони на листа.
Изход
На стандартния изход изведете едно цяло число – броя различни начини, по които може да бъде запълнен листът. Тъй като отговорът може да бъде много голям, изведете само неговия остатък при деление на 1,000,000,007.
Ограничения
  • 1 ≤ N, M ≤ 50
Примерен Вход Примерен Изход
3 3 284
5 4 898416
13 17 390317257
42 42 193467102
Мрън!