Сімейна естафета
Уряд Байтландії оголосив 2012 рік Роком здоров'я. У зв'язку з цим було вирішено побудувати бігову доріжку в національному столичному парку для проведення щорічної сімейної естафети. Парк має форму прямокутника розміром N на M метрів, розділеного на квадрати однакового розміру площею один м². Іншими словами, парк можна уявити як прямокутну таблицю з N рядками і M стовпцями. Рядки нумеруються зверху вниз, починаючи з одиниці, а стовпці — зліва направо, також починаючи з одиниці. Таким чином, кожному квадрату відповідає пара чисел (X, Y), де X — номер рядка, а Y — номер стовпця, на перетині яких він знаходиться.
Спочатку планувалося зробити бігову доріжку у вигляді прямокутника. Однак, згідно з рекомендаціями екологів Міністерства природних ресурсів Байтландії, її слід зробити у формі хреста, відповідно до світових стандартів.
Бігова доріжка у формі хреста будується наступним чином:
обирається горизонтальна смуга шириною один квадрат і довжиною H квадратів;
обирається вертикальна смуга шириною один квадрат і довжиною V квадратів, яка перетинається з горизонтальною смугою, де H і V — будь-які натуральні числа (квадрат, що належить одночасно горизонтальній і вертикальній смугам, називається базовим);
по всій довжині кожної зі смуг посередині встановлюються огорожі довжиною H - 1 і V - 1 метрів відповідно.
Естафета починається і закінчується в базовому квадраті. Забіг здійснюється вздовж огорожі бігової доріжки, як це показано на рисунку.
Рисунок №1. Опис другого прикладу, 2 можливих варіанти доріжки вартістю по 6 байт.
Квадрати парку можуть бути двох типів: містять дерево або не містять дерево (порожній квадрат). Вважатимемо, що якщо квадрат містить дерево, то воно займає всю його площу.
Вартість будівництва бігової доріжки залежить не тільки від кількості квадратів, але й від їх типу. Відомо, що вартість обладнання порожнього квадрата для бігової доріжки становить один байт (байт — національна валюта Байтландії), а обладнання квадрата, що містить дерево, становить два байти, оскільки дерево потребує попереднього знесення.
На створення бігової доріжки уряд Байтландії виділив S байт. Ваше завдання — визначити кількість різних способів побудови бігової доріжки у формі хреста. Два способи побудови вважаються різними, якщо відрізняються множини відповідних їм квадратів або базові квадрати.
Вхідні дані
Перша рядок вхідного файлу містить три цілі числа, розділених пробілами: N, M (2 ≤ N, M ≤ 300) і S (1 ≤ S ≤ 10^9).
Наступні N рядків містять рядкові величини, що складаються з M символів, які описують парк. j-й символ у i-й рядковій величині описує тип квадрата. Символ '.' (ASCII 46) означає, що квадрат з координатами (i, j) є порожнім, символ '#' (ASCII 35) означає, що квадрат з координатами (i, j) містить дерево.
Вихідні дані
Вихідний файл повинен містити одне ціле число — кількість різних способів побудови бігової доріжки у формі хреста.