Z - Zásobník

Profesor Algoda pri kontrole úloh zistil, že študenti sú stále vynaliezavejší a opisujú prefíkanejšie. Keďže úlohy sa už dlhšie odovzdávajú elektronicky, tak sa automaticky kontroluje zhoda medzi riešeniami. To naučilo študentov meniť názvy premenných v programe a robiť ďalšie úpravy, aby sa vyhli automatickej detekcii. Po posledných úlohách ale zistil, že veľa riešení bolo podozrivo rovnako zlých v jednom konkrétnom prípade. Rozhodol sa preto zaviesť inovatívne riešenie odovzdávania úloh. Úloha bude mať viacero riešení, ale každé riešenie môže byť odovzdané iba raz, teda ráta sa iba prvému. Ostatní musia nájsť iné riešenie.
Pri tvorbe úlohy k zásobníku ale zistil, že to nie je také jednoduché (aby pri takom množstve študentov mohol každý mať iné riešenie). Pomôžte mu zistiť koľko rôznych riešení existuje. Zásobník ako dátová štruktúra podporuje dve operácie - PUSH (vloženie) a POP (vybratie). Úloha spočíva v doplnení neúplnej postupnosti operácií PUSH a POP tak, aby postupnosť reprezentovala korektný zápis (vyberáme iba ak sa ešte v zásobníku nachádza aspoň jeden prvok, skončíme s prázdnym zásobníkom).

Úloha

Pre zadané čiastočné informácie z postupnosti popisujúcej korektný zápis operácií, nájdite počet možných korektných riešení.

Vstup

Prvý riadok obsahuje jedno celé číslo, počet testovacích sád 1 < T < 1000. Nasleduje T riadkov obsahujúcich reťazec zložený zo znakov + (znamená PUSH), - (POP), . (neznámy znak, ktorý majú študenti doplniť). Dĺžka jedného reťazca nepresiahne 1000 znakov.

Výstup

Výstupom programu je jedno číslo, počet možností - jeho posledných 6 cifier.

Príklad

Vstup:

4
....
.+..
-...
...-....................

Výstup:

2
1
0
75582