Problem D
Hackenbush lúpínur

Sýniinntök 1, 2, 3

Hackenbush er leikur með leggjum af þremur litum sem tengjast í hvorn annan eða jörð. Leggirnir eru allir rauðir, bláir eða grænir. Annar leikmaður getur hoggið rauða og græna leggi og hinn leikmaðurinn bláa og græna leggi. Þegar leikmaður heggur legg er honum eytt út. Einnig er öllum leggjum sem hafa ekki leið niður í jörð um aðra leggi eytt út.

Gildi Hackenbush leiks með rauðum og bláum leggjum er skilgreint í nokkrum skrefum. Við segjum að stakur blár leggur sé $+1$, stakur rauður leggur sé $-1$. Eins segjum við að staða þar sem sá sem leikur fyrst tapar ávallt hafi gildi $0$. Með því að bera saman stöður og fá hvenær summan er núll getum við þá fundið gildi nýrra staða. Tökum sem dæmi bláan legg fest við rauðan legg sem er fest í jörð. Ef við tökum tvö eintök af þeirri stöðu og svo einn stakann bláann legg fæst staða sem hefur gildið $0$. Þar með er gildi stöðunnar sem við erum að skoða $-1/2$.

Þú færð gefna stöðu af Hackenbush lúpínum. Þetta er staða í leiknum Hackenbush þar sem allir leggir eru bláir eða rauðir og allir leggir liggja á beinum strikum frá jörðu sem skiptast ekki.

Þú þarft að ákvarða gildi leiksins. Sýna má að þetta er ávallt heiltölubrot.

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $0 \leq n \leq 100$, fjöldi stöngla. Næst fylgja $n$ línur, hver með einum stöngli. Hverjum stöngli er lýst með streng sem inniheldur aðeins stafina R og B. R táknar rauðan legg og B bláan legg. Fyrsti stafurinn táknar legginn sem snertir jörðina, næsti stafur er leggurinn þar fyrir ofan og svo koll af kolli. Hæð hvers stönguls er einnig mest $10^3$.

Úttak

Ef gildi leiksins er $p/2^q$ prentið p/2q þar sem $p/2^q$ er fullstytt brot. Ef brotið er heiltala, prentið gildið án /20. Gildi leiksins er ávallt á þessu formi.

3
RB
RR
BB

-1/2^1

1
BBR

3/2^1

1
BRRB

3/2^3

3
BBB
RRRR
BB

1