Imamo robota kome se mogu zadati 3 različite komande:

• P - govori robotu da se pomeri za 1 metar unapred u pravcu u kome je okrenut,
• L - govori robotu da se okrene za 90° u levo u mestu (lokacija mu se ne menja),

• D - govori robotu da se okrene za 90° u desno u mestu (lokacija mu se ne menja).

  Dato je K blokova od po N ovakvih komandi, blokovi se mogu izvršiti u bilo kom redosledu, dok se komande unutar jednog bloka moraju izvršiti u redosledu u kome su date. Svi blokovi se moraju izvršiti. Odrediti u koliko razliqitih redosleda izvršavanja blokova komandi će se robot na kraju naći nazad u istom mestu iz koga je pošao.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke sa nalaze dva broja K i N (1 ≤ K ≤ 8, 1 ≤ N ≤ 100.000). U sledećih K redova nalazi se po N znakova od kojih je svaki P, L ili D.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu izlaza ispisuje se traženi broj redosleda izvršavanja blokova komandi.

Primer:

3 4
PPLP
PLPD
LPLD

1

Objašnjenje.

Ako je robot na početku okrenut ka severu, dati su svi mogući redosledi izvršavanja blokova komandi i relativna pozicija robota na kraju u odnosu na početnu tačku.

• 1 - 2 - 3 [PPLP—PLPD—LPLD] 0 metara na sever, 2 metara na zapad
• 1 - 3 - 2 [PPLP—LPLD—PLPD] 0 metara na sever, 0 metara na istok
• 2 - 1 - 3 [PLPD—PPLP—LPLD] 2 metara na sever, 2 metara na zapad
• 2 - 3 - 1 [PLPD—LPLD—PPLP] 0 metara na sever, 4 metara na zapad
• 3 - 1 - 2 [LPLD—PPLP—PLPD] 2 metara na jug, 2 metara na zapad

• 3 - 2 - 1 [LPLD—PLPD—PPLP] 2 metara na jug, 4 metara na zapad

  Samo u drugom slučaju kada se blokovi izvršavaju u redosledu 1 - 3 - 2 se robot na kraju nalazi u istoj tački odakle je počeo.

Napomena.

U 30% test primera biće K ≤ 6 i N ≤ 1000.