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 ≠ 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 ≤ n ≤ 20.

Sortida

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