Subconjunts tranquils P91562

Esteu planificant un viatge per als $n$ membres d’un club. Tanmateix, a alguns dels membres no els agraden altres membres. Per tant, decidiu escollir un subconjunt $S$ dels membres tal que, dins d’$S$, a ningú li desagradi ningú.

Donada tota la informació de a qui li desagrada qui, podeu comptar el nombre d’aquests subconjunts?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ seguida d’$n$ línies amb $n$ caràcters cadascuna. Per a $i \ne j$, el caràcter $j$-èsim de la $i$-èsima línia és ‘A’ o ‘D’ depenent de si a $i$ li agrada o li desagrada $j$. La diagonal només té punts. Assumiu $1 \le n \le 20$.

Sortida

Per a cada cas, escriviu el nombre de subconjunts tranquils que no siguin buits.