Задача D. Don't understarve ≡

Условие

Уилсон заблудился в пещере размером N × M клеток. Но у него есть карта, на которой приняты следующие обозначения:

'#' — непроходимая клетка (пропасть, стена);

'.' — свободная клетка;

'X' — червоточина, при переходе в эту клетку Уилсон равновероятно переместится в одну из других червоточин;

'S' — начальное положение Уилсона;

'F' — клетка, до которой нужно добраться (выход на поверхность).

Перемещение через червоточину — процесс рискованный, так как при этом очень сильно падает рассудок. А при низком рассудке могут начать нападать монстры.

Рассудка Уилсона хватит ровно на одно перемещение. Поэтому он хочет узнать вероятность выбраться из пещеры, используя при этом не более одной червоточины. Разумеется, Уилсон действует оптимально, то есть он старается максимизировать вероятность.

Уилсон может перемещаться в четырех возможных направлениях: вверх, вниз, вправо, влево.

Обратите внимание, что Уилсон не может наступить в червоточину при этом не переместившись.

Формат входных данных

В первой строке содержится два целых числа N и M — размеры пещеры.

Далее следует N строк по M символов — карта пещеры.

Гарантируется, что на карте всегда присутствует одна клетка 'S', как минимум одна клетка 'F', и как минимум две клетки 'X'.

Формат выходных данных

Выведите ответ как обыкновенную несократимую дробь в виде двух целых чисел, разделённых пробелом (например, если ответ 50 / 74, нужно вывести "25 37").

Ограничения

2 ≤ N, M ≤ 1000

Примеры тестов

2 2
XX
SF

1 1

4 4
#F.X
##X#
X#SX
###F

2 3

2 5
.F#S.
XXXXX

1 2

3 5
.F#S.
.#X#.
X..X#

0 1