У Ральфа есть магическое поле, которое разделено на n × m блоков. А именно, на поле есть n строк и m столбцов. Ральф хочет в каждый блок поставить целое число. Однако, магическое поле не всегда работает правильно. Оно работает, только если произведение чисел в каждой строке и в каждом столбце равно k, где k может быть равно 1 или -1.

Ральф хочет узнать количество способов поставить некоторые целые числа во все блоки так, чтобы магическое поле работало правильно. Два способа считаются различными, если и только если существует хотя бы один блок такой, что числа в нем в первом и втором способе различны. Вам необходимо вывести остаток от деления ответа на 1000000007 = 10⁹ + 7.

Обратите внимание, нет ограничения на целые числа, которые можно ставить в блоки, однако, можно показать, что ответ конечный.