Створення Підземелля
Король демон чекає у своєму підземеллі, щоб перемогти хороброго чоловіка. Його підземелля складається з H×W клітинок. Кожна клітинка з'єднана з чотирма сусідніми клітинками (північ, південь, схід і захід), і деякі з них зайняті перешкодами.
Щоб атакувати хороброго чоловіка, король демон створив і відправив слугу, який блукає по підземеллю. Однак незабаром король демон виявив, що слуга не працює так, як він хоче. Слуга занадто дурний. Якщо в підземеллі є циклічний шлях, він може продовжувати ходити по циклу вічно.
Щоб переконатися, що слуга зрештою знайде хороброго чоловіка, король демон вирішив усунути всі цикли, будуючи стіни між клітинками. Водночас він повинен бути обережним, щоб між будь-якими двома клітинками, не зайнятими перешкодами, був принаймні один шлях.
Ваше завдання - написати програму, яка обчислює, скількома способами король демон може побудувати стіни.
Вхідні дані
Перша строка кожного тестового випадку містить два цілі числа H і W (1 ≤ H ≤ 500, 1 ≤ W ≤ 15), які є висотою і шириною підземелля. Наступні H рядків складаються з точно W символів, кожен з яких є '.' (на клітинці немає перешкоди) або '#' (на клітинці є перешкода). Ви можете припустити, що є принаймні одна клітинка, яка не має перешкоди.
Вхід завершується, коли H=0 і W=0. Ваша програма не повинна виводити для цього випадку.
Вихідні дані
Для кожного тестового випадку виведіть номер випадку та кількість способів, якими можна побудувати стіни, в одному рядку. Оскільки відповідь може бути дуже великою, виведіть у модулі 1000000007.