Один спільний коридор#13119
Місто має вигляд прямокутної таблиці з рядків і стовпців. Рядки пронумеровано згори вниз, а стовпці — зліва направо. Кожна клітинка є або вільною, або заблокованою.
Два кур'єри мають пройти через місто. За один крок кожен кур'єр може перейти в сусідню вільну клітинку праворуч або вниз.
Перший кур'єр починає рух у клітинці і повинен завершити його в . Другий кур'єр починає рух у клітинці і повинен завершити його в .
Два маршрути називаються узгодженими, якщо їхні спільні клітинки утворюють одну неперервну частину обох маршрутів, що містить щонайменше дві клітинки. Ця спільна частина може містити повороти.
Формально мають існувати дві різні клітинки та на обох маршрутах, для яких виконуються такі умови:
До клітинки маршрути не мають спільних клітинок.
Від до включно обидва кур'єри проходять ту саму послідовність клітинок.
Після клітинки маршрути не мають спільних клітинок.
Отже, зустріч лише в одній клітинці не підходить. Також не підходять маршрути, які розходяться, а згодом знову зустрічаються.
Знайдіть кількість узгоджених пар маршрутів за модулем 10^9+7. Кур'єри різні: пара визначається маршрутом першого та маршрутом другого кур'єра.
У першому рядку задано два цілі числа і (3\leq h,w\leq2000).
У другому рядку задано чотири цілі числа a,b,c,d (2\leq a,d\leq w-1; 2\leq b,c\leq h-1).
Кожен із наступних рядків містить символів, кожен із яких є . або #. Символ . позначає вільну клітинку, а # — заблоковану.
Гарантовано, що клітинки , , та вільні.
Виведіть одне ціле число — кількість узгоджених пар маршрутів за модулем 10^9+7. Якщо таких пар немає, виведіть .
Приклад 1
Приклад 2
Приклад 3
У першому прикладі є одна узгоджена пара маршрутів. Їхня спільна частина складається з клітинок та .
У другому прикладі маршрути можуть мати лише одну спільну клітинку , тому відповідь дорівнює .
У третьому прикладі є узгоджених пар маршрутів.
Підзадача ( балів): h,w\leq6.
Підзадача ( балів): h,w\leq20.
Підзадача ( балів): h,w\leq70.
Підзадача ( балів): \min(h,w)\leq6.
Підзадача ( балів): немає заблокованих клітинок.
Підзадача ( балів): a=d або b=c.
Підзадача ( балів): без додаткових обмежень.