Помогите решить олимпиаду python

Question

Недавно в Байтбурге построили новый район. Он состоит из n 
рядов по m 
домов, расположенных в виде прямоугольной сетки n×m 
. Для простоты будем считать каждый дом точкой на плоскости. Тогда дома расположены в точках с целыми координатами (x,y) 
для всех x 
и y 
, удовлетворяющих 1≤x≤n 
и 1≤y≤m 
. 
Главный архитектор хочет покрасить дома в два цвета — красный и синий, так чтобы выполнялись следующие свойства. 
Есть хотя бы один дом, покрашенный в красный цвет, и хотя бы один дом, покрашенный в синий цвет. 
Можно построить прямую линию, не проходящую через дома, так чтобы все дома с одной стороны от неё были синими, а с другой стороны — красными. 
Помогите главному архитектору понять, сколько есть различных способов покрасить дома, удовлетворяющих этим свойствам. 
Входные данные 
Ввод содержит два целых числа n 
и m 
(1≤n,m≤20 
). 
Выходные данные 
Выведите одно число — число способов покрасить дома. 
Примеры 
Входные данныеСкопировать 
2 2 
Выходные данныеСкопировать 
12 
Входные данныеСкопировать 
5 1 
Выходные данныеСкопировать 
8 
Входные данныеСкопировать 
20 20 
Выходные данныеСкопировать 
97868 
Примечание 
Ниже изображены все 12 способов для первого примера:

polina_sivokon_3 · Accepted Answer

всего способов покрасить дома будет так: у нас 2 цвета и линии рисуем, считай 2^nm-2, потом учти, что линии блин можно проводить вокруг системно, скачай все варианты и посчитай что нарисовано неразличимо, вот и ответ, успехов!