Наскельні малюнки
Бессі стала художницею і малює печери! Зараз вона працює над картиною висотою n, де кожен рядок містить рівно m квадратів. Кожен квадрат може бути або порожнім, або заповненим каменем, або заповненим водою. Бессі вже намалювала квадрати з каменем, включаючи всю межу картини. Тепер вона хоче заповнити водою деякі порожні квадрати так, щоб, якби картина була справжньою, вода не могла б текти по ній. Визначимо висоту квадрата в i-му рядку зверху як n + 1 − i. Бессі хоче, щоб її картина відповідала наступному обмеженню:
Припустимо, що квадрат a заповнений водою. Тоді, якщо існує шлях від a до квадрата b з використанням лише порожніх квадратів або квадратів з водою, висота яких не перевищує висоту a, і кожні два сусідні квадрати на шляху мають спільну сторону, тоді квадрат b також повинен бути заповнений водою.
Знайдіть кількість різних картин, які Бессі може створити, за модулем 10^9 + 7. Бессі може заповнити водою будь-яку кількість порожніх квадратів (усі або жодного).
Вхідні дані
Перша строка містить два цілих числа n і m (1 ≤ n, m ≤ 1000). Кожен з наступних n рядків містить m символів. Кожен символ - це або '.', або '#', що представляє порожній квадрат і квадрат, заповнений каменем, відповідно. Перший і останній рядок, а також перший і останній стовпці містять тільки '#'.
Вихідні дані
Виведіть одне ціле число: кількість картин, що задовольняють обмеженню за модулем 10^9 + 7.
Приклад
Якщо квадрат у другому рядку заповнений водою, то всі порожні квадрати повинні бути заповнені водою. В іншому випадку, припустимо, що такі квадрати не заповнені водою. Тоді Бессі може заповнити будь-яку підмножину з трьох суміжних по горизонталі областей порожніми квадратами в третьому рядку. Таким чином, кількість картин дорівнює 1 + 2^3 = 9.