Zapis

Μια κανονική ακολουθία αγκύλων είναι μια σειρά χαρακτήρων που αποτελείται μόνο από αγκύλες ανοίγματος και κλεισίματος και πληροί τις ακόλουθες προϋποθέσεις:

• Μια κενή συμβολοσειρά είναι μια κανονική ακολουθία αγκύλης.
  
• Αν η ~A~ είναι μια κανονική ακολουθία αγκύλων, τότε οι ~(A)~, ~[A]~ και ~\{A\}~ είναι επίσης κανονικές ακολουθίες αγκύλων.
  
• Αν οι ~A~ και ~B~ είναι κανονικές ακολουθίες αγκύλων, τότε η ~AB~ είναι επίσης κανονική ακολουθία αγκύλης.

Για παράδειγμα, οι ακολουθίες ~[(\{\})]~, ~[]()\{\}~ και ~[\{\}]()[\{\}]~ είναι κανονικές, αλλά οι ακολουθίες ~[(\{\{([~, ~[](\{)\}~ και ~[\{\}])([\{\}]~ δεν είναι.
Ο Ivica βρήκε μια συμβολοσειρά που μοιάζει να είναι μια κανονική ακολουθία αγκύλων. Μερικοί από τους χαρακτήρες έχουν γίνει μουντζούρες, είναι δυσανάγνωστοι και θα μπορούσαν να είναι οποιοσδήποτε χαρακτήρας.
Γράψτε ένα πρόγραμμα που να υπολογίζει με πόσους τρόπους μπορούν να αντικατασταθούν οι δυσανάγνωστοι χαρακτήρες στη συμβολοσειρά αγκύλες έτσι ώστε το αποτέλεσμα να είναι μια κανονική ακολουθία αγκύλων. Αυτός ο αριθμός μπορεί να είναι πολύ μεγάλος, επομένως τυπώστε μόνο τα τελευταία 5 ψηφία του.

Είσοδος

Η πρώτη γραμμή περιέχει έναν άρτιο ακέραιο ~N(2\le N\le 200)~, το μήκος της συμβολοσειράς.
Η δεύτερη γραμμή περιέχει τη συμβολοσειρά. Οι δυσανάγνωστοι χαρακτήρες αντιπροσωπεύονται από το "?".

Έξοδος

Τυπώστε τον αριθμό των κανονικών ακολουθιών αγκύλων που θα μπορούσε να έχει διαβάσει ο Ivica.

Παραδείγματα

input

6
() () ()

output

1

input

10
(?([?)]?}?

output

3

Επεξήγηση του 2ου παραδείγματος:

Οι τρεις αντίστοιχες κανονικές ακολουθίες αγκύλων είναι ~(\{([()])\})~, ~()([()]\{\})~ και ~([([])]\{\})~.

input

16
???[???????]????

output

92202