Robot Naviqasiyası#3339
Bir robot uzaq bir planetə kəşfiyyat üçün göndərilib. Robotun izləməli olduğu yolu müəyyən etmək üçün hər gün bir proqram göndərilir. Proqram aşağıdakı əmrlərin ardıcıllığından ibarətdir:
İRƏLİ X: X vahid irəli hərəkət et.
SOL DÖN: 90 dərəcə sola dön (yerində).
SAĞ DÖN: 90 dərəcə sağa dön (yerində).
Robotun ətraf mühitini xəritələndirmək üçün sensor vahidləri də var. Xəritə bir tor şəbəkəsi kimi təmsil olunur. Bəzi tor nöqtələri təhlükələr (məsələn, kraterlər) ehtiva edir və proqram bu nöqtələrdən qaçmalı və ya robotu itirmək riski ilə üzləşməlidir.
Əgər robotun ilkin yeri, üzləşdiyi istiqamət və təyinat nöqtəsi məlumdursa, robotu təyinat nöqtəsinə aparmaq üçün ən qısa proqramı (ən az əmr olan) göndərmək daha yaxşıdır (təyinatda hansı istiqamətə baxdığı əhəmiyyətli deyil). Siz robotu təyinat nöqtəsinə aparacaq fərqli ən qısa proqramların sayını bilməkdə maraqlısınız. Lakin, ən qısa proqramların sayı çox böyük ola bilər, buna görə də qalıq olaraq 1,000,000-ə görə sayını hesablamaqla kifayətlənirsiniz.
Girişdə bir neçə test halı olacaq. Hər test halı iki tam ədədlə başlayan bir sətirlə başlayacaq:
N M
Burada N tor şəbəkəsindəki sətirlərin sayı, M isə sütunların sayıdır (2 ≤ N, M ≤ 100). Girişin növbəti N sətiri hər biri M simvolu olacaq. Simvollar aşağıdakılardan biri olacaq:
'.' Naviqasiya edilə bilən tor nöqtəsini göstərir.
'*' Krater (yəni naviqasiya edilə bilməyən tor nöqtəsi) olduğunu göstərir.
'X' Məqsəd tor nöqtəsini göstərir. Dəqiq bir 'X' olacaq.
'N', 'E', 'S', və ya 'W' Robotun başlanğıc nöqtəsini və ilkin istiqamətini göstərir. Dəqiq bir bunlardan biri olacaq. Qeyd edək ki, istiqamətlər xəritədəki kompas istiqamətlərini əks etdirir: N Şimaldır (torun yuxarısına doğru), E Şərqdir (torun sağ tərəfinə doğru), S Cənubdur (torun aşağısına doğru) və W Qərbdir (torun sol tərəfinə doğru).
Xəritə təsvirində boşluqlar və başqa simvollar olmayacaq. Giriş iki 0 ilə bitən bir sətirlə sona çatacaq.
Hər test halı üçün bir sətirdə iki tam ədəd çıxış edin, aralarında bir boşluq ilə. Birincisi, robotu başlanğıc nöqtəsindən məqsədə aparmaq üçün mümkün olan ən qısa proqramın uzunluğudur, ikincisi isə həmin uzunluqda robotu məqsədə aparacaq fərqli proqramların sayıdır (modulo 1,000,000). Əgər robotdan məqsədə bir yol yoxdursa, bir boşluq ilə ayrılmış iki sıfır çıxış edin. Əlavə boşluqlar çıxış etməyin və cavabları boş sətirlərlə ayırmayın.
Nümunə 1