Дужки

Давайте визначимо правильний рядок дужок наступним чином:

• () і [] є правильними рядками дужок;

• якщо A є правильним рядком дужок, тоді (A) і [A] також є правильними рядками дужок;

• якщо A і B обидва є правильними рядками дужок, тоді конкатенація AB також є правильним рядком дужок;

У правильному рядку дужок, що містить принаймні одну пару квадратних дужок: [ і відповідну ], кожна квадратна дужка (як відкрита, так і закрита) була замінена на відкриту круглу дужку, утворюючи зламаний рядок дужок.

Наприклад, (( і ((((())) обидва є зламаними рядками дужок. Перший рядок отримано з правильного рядка дужок []. Другий рядок може бути отриманий лише з наступних чотирьох правильних рядків дужок: []((())), ([](())), (([]())) або ((([]))).

Ваше завдання - для даного зламаного рядка дужок обчислити кількість можливих правильних рядків дужок, з яких міг бути отриманий даний зламаний рядок.