Доміно
Дора любить грати в доміно. Вона бере таблицю розміром n * m, позначає деякі клітинки як зайняті, а потім намагається заповнити всі незайняті клітинки доміношками розміром 2 * 1.
Її молодший брат Дені любить жартувати над своєю старшою сестрою. Тому, коли вона відсутня, він позначає ще дві незайняті клітинки як зайняті. Він хоче зробити це так, щоб усі незайняті клітинки не можна було заповнити доміношками.
Допоможіть Дені порахувати, скількома способами він може вибрати ці дві клітинки. Оскільки Дені вміє рахувати лише до одного мільйона, якщо ця кількість способів дорівнює x, то виведіть min(x, 10^6).
Вхідні дані
Перша стрічка містить цілі числа n і m (1 ≤ n, m ≤ 1000). Наступні n рядків містять по m символів у кожному - початковий стан таблиці. Символ "#" відповідає зайнятій клітинці, а символ "." - пустій клітинці. Гарантується, що є як мінімум дві незайняті клітинки і що всі вільні клітинки можна заповнити доміношками.
Вихідні дані
Нехай x - кількість способів, якими Дені може позначити дві клітинки так, що всі незайняті клітинки не можна буде заповнити доміношками.
Виведіть одне ціле число min(x, 10^6).