Sokkelo

• Time limit: 1.00 s
• Memory limit: 128 MB

Annettuna on kuvaus $n \times m$ -sokkelosta, joka muodostuu lattia- ja seinäruuduista. Lisäksi sokkelossa on lähtöruutu ja maaliruutu.

Robotti liikkuu sokkelossa $k$ askelta alkaen lähtöruudusta. Robotti voi liikkua vasemmalle, oikealle, ylöspäin ja alaspäin, mutta vain ruutuihin, joissa ei ole seinää, eikä ruudukon ulkopuolelle.

Joka askeleella robotti valitsee satunnaisesti, mihin suuntaan se liikkuu, niiden viereisten ruutujen joukosta, joihin se voi liikkua. Jokaisen ruudun todennäköisyys tulla valituksi on sama.

Tehtäväsi on laskea todennäköisyys, että robotti on maaliruudussa tasan $k$ askeleen jälkeen.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua $n$, $m$ ja $k$, jotka ilmaisevat sokkelon koon ja askelten määrän.

Sitten syötteessä on $n$ riviä, joista jokaisella on $m$ merkkiä. Nämä rivit kuvaavat sokkelon. Mahdolliset merkit ovat # (seinä), . (lattia), A (lähtö) ja B (maali). Merkkejä A ja B on molempia tasan yksi.

Tuloste

Tulosta todennäköisyys, että robotti päätyy maaliruutuun $k$ askeleen jälkeen.

Tulosta vastaus pyöristettynä niin, että siinä on tasan 6 desimaalia.

Rajat

• $1 \le n,m \le 10$
  
• $1 \le k \le 100$
  

Esimerkki

Syöte:
3 4 3
#A##
#.##
B..#

Tuloste:
0.166667