Da file input.txt leggiamo un numero pari n seguito da una stringa di lunghezza n su un alfabeto di tre soli caratteri: '*', '(' e ')'.

input.txt
8
*(*())**

Ci chiediamo in quanti modi diversi sia possibile sostituire delle parentesi agli asterischi in modo da ottenere una formula ben formata.
Nell'esempio di cui sopra vi sono solamente 2 modi:

(((())))
(()())()
 
e riceviamo pertanto punteggio pieno su questa istanza scrivendo su directory corrente il file

output.txt
2

Piu' in generale, per evitare overflow, e' chiesto di scrivere su output.txt solamente le ultime 5 cifre del numero di formule ben formate di parentesi compatibili con la maschera data nel file input.txt, ossia tale numero modulo 100000. 


Assunzioni:
 - tempo limite = 1 secondo (user time),
 - massima memoria statica = 400 Mb;
 - n <= 500000,
 - la stringa in input contiene massimo 1000 asterischi.
 - in almeno  5 istanze n <= 10.
 - in almeno 12 istanze n <= 10000.

Note:
 - Garantiamo che esista sempre almeno una formula ben formata compatibile con il pattern assegnato.
 - Lascio a disposizione nella directory del problema anche i miei codici per la produzione di istanze tipo quelle su cui verra' effettuata la valutazione.