У Ральфа есть магическое поле, которое разделено на n × m блоков. А именно, на поле есть n строк и m столбцов. Ральф хочет в каждый блок поставить целое число. Однако, магическое поле не всегда работает правильно. Оно работает, только если произведение чисел в каждой строке и в каждом столбце равно k, где k может быть равно 1 или -1.
Ральф хочет узнать количество способов поставить некоторые целые числа во все блоки так, чтобы магическое поле работало правильно. Два способа считаются различными, если и только если существует хотя бы один блок такой, что числа в нем в первом и втором способе различны. Вам необходимо вывести остаток от деления ответа на 1000000007 = 109 + 7.
Обратите внимание, нет ограничения на целые числа, которые можно ставить в блоки, однако, можно показать, что ответ конечный.
Примечание
В первом примере единственный способ — поставить -1 в единственный блок.
Во втором примере единственный способ — поставить 1 в каждый блок.