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