Un pacman cerca di raggiungere un pillolozzo in una griglia rettangolare mxn fatta di celle libere e di celle muro.
Il pacman e' inseguito da un'orda di fantasmini e, ad ogni mossa, puo' rimanere fermo oppure muoversi ad una qualsiasi delle (massimo 4) celle libere adiacenti la cella attualmente occupata. Le mosse dei fantasmini seguono le stesse regole, con la differenza che essi possono portarsi anche su celle muro.
Il pacman vince se riesce a raggiungere un qualsiasi pillolazzo (strettamente)
prima di trovarsi nella stessa cella di un fantasmino.
Tuttavia il pacman e' chiamato a dichiarare in anticipo il pillolazzo
che intende raggiungere ed il percorso che intende fare,
ed i fantasmini si avvarranno di tale informazione per giocare in modo ottimo. 

Esempio: Su una griglia 3x6, oltre al pacman (M) sono collocati 5 pillolazzi (P) ed 1 fantasmino (F). Le celle contrassegnate W (wall) sono di muro, mentre le altre sono tutte libere.
Contrassegnamo con una L tutte le celle non altrimenti contrassegnate.


input.txt
3 6
M P P W L P
F P L L W W
W W L P L W

In questo caso il pacman ha due modi per vincere: o dichiara che intende compiere il percorso che visita le celle (1,1)-(1,2) oppure dichiara il percorso (1,1)-(1,2)-(1,3):

output.txt
2

Se modifichiamo l'esempio in:

input.txt
3 6
M P P W L P
F P L F W W
W W L P L W

allora il secondo piano viene sconfitto col
nuovo fantasmino che percorre le celle (2,4)-(2,3)-(1,3): 

output.txt
1

Come ulteriore esempio, un caso in cui il pacman puo' prendesi le sue mosse di attesa:

input.txt
4 5
M L W L F
L P L L L
L L W W L
L L P W F

output.txt
8

Cui corrispondono gli 8 piani:
(1,1)-(2,1)-(2,2)
(1,1)-(1,2)-(2,2)
(1,1)-(2,1)-(2,2)-(2,2)
(1,1)-(1,2)-(2,2)-(2,2)
(1,1)-(2,1)-(2,1)-(2,2)
(1,1)-(1,2)-(1,2)-(2,2)
(1,1)-(1,1)-(2,1)-(2,2)
(1,1)-(1,1)-(1,2)-(2,2)

ASSUNZIONI: m,n <= 100, il numero di output corretti trovera' sempre spazio in una varibile di tipo <long long int>, tempo limite = 3 secondi.