Алекс тестирует навигацию в музее. План музея — прямоугольная таблица из n строк и m столбцов. Клетка # занята стеной, клетка . свободна. В клетке S находится Алекс, а в клетке T — пульт управления.
За один шаг можно перейти в соседнюю по стороне свободную клетку. Клетки S и T тоже свободны. Выходить за границы таблицы нельзя.
Найдите минимальное количество шагов от S до T и число различных маршрутов такой длины. Маршруты различны, если различаются последовательности посещённых клеток. Количество маршрутов выведите по модулю 1 000 000 007.
Входные данные
Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 500, 2 ≤ nm ≤ 200 000). Далее идут n строк по m символов ., #, S, T. Символы S и T встречаются ровно по одному разу и находятся в разных клетках.
Выходные данные
Выведите два целых числа: длину кратчайшего маршрута и количество таких маршрутов по модулю 1 000 000 007. Если пульт недостижим, выведите -1 0.
Пояснения к примерам
Пример 1. Можно обойти стены сверху и справа либо слева и снизу. Оба маршрута содержат пять шагов.
Пример 2. Стена полностью перекрывает путь.
| № | Входные данные | Выходные данные |
|
1
|
3 4
S...
.##.
...T
|
5 2
|
|
2
|
1 3
S#T
|
-1 0
|