Недавно оказалось, что все экономическое состояние Берляндии на данный момент можно описать при помощи простой таблицы размера n × m. n — количество дней в каждом берляндском месяце, m — количество месяцев. Таким образом, клетка таблицы соответствует дню и месяцу берляндского года. В каждой клетке будет записано либо 1, либо -1, что означает доход государства в какой-то конкретный месяц и день, где 1 соответствует прибыли, -1 соответствует убытку. Для успешного развития оказалось важным проанализировать данные об экономическом состоянии прошлого года, но когда казначеи обратились в архив за данными, оказалось, что таблица была очень существенно испорчена. В некоторых клетках таблицы значения чисел стерлись, и теперь разобрать их невозможно. Известно, что количество клеток, где данные сохранились, строго меньше max(n, m). Однако, есть дополнительная информация — произведение чисел в каждой строке и в каждом столбце было равно -1. От вас требуется найти, сколько различных таблиц может соответствовать данным, которые сохранились. Так как ответ на задачу может быть достаточно большим, требуется найти его по модулю p.