Problem B: Cleaning Robot

ロボット工学の研究者であるアシモフ博士は、研究が大好きだけれども、家事は全く好きではなかった。なので彼の自宅はとても汚れていた。そこで彼は、彼の家を掃除してくれるロボットを開発した。

彼の家には、以下のような9つの部屋があり、それぞれ A から I の名前がついている。

そして彼が開発したロボットは、以下のように動作する:

もしバッテリーが残っていなければ停止する。そうでなければ、東西南北のいずれかの方向を等確率で選び、その方向の隣の部屋に移動し、その部屋を掃除し、バッテリーを1ポイント消費する。
ただし、もし進もうとする方向に部屋がなければ、移動せずにその部屋に留まる。また、博士の家には物置として使っている部屋が 1 室あり、その部屋へ入ろうとしたときも移動せずにその部屋に留まる。ロボットは移動しなかったときでも同じようにバッテリーを消費する。

ロボットのバッテリーの充電器は、博士の家のとある部屋に設置されている。ロボットが停止したとき、ちょうど充電器のある部屋にいたなら、博士にとって都合が良い。そのようなことが起きる確率を求めるプログラムを書いてほしい。

Input

入力ファイルは、複数のデータセットから構成される。１つのデータセットは、以下の形式で与えられる:

n
s t b

n はバッテリーの残ポイント数を示す整数である。 s, t, b はそれぞれ、最初にロボットがいる部屋、充電器のある部屋、倉庫として使っている部屋を示す大文字のアルファベットである。

入力の終了は、n = 0 であるデータセットによって示される。このデータセットに対して出力をしてはならない。

各データセットについて、確率を浮動小数点数で1行に出力せよ。出力は0.000001以下の誤差を含んでもよい。

1
E A C
1
E B C
2
E A B
0

0.00000000
0.25000000
0.06250000