АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
News FAQ E-learning
For authors:
Register  ||  Login
Forgot your password?
Authors ranklist
 
About project
Hello, Guest! Please login or register.

67. Restoration of Brackets

Time Limit: 1 seconds
Memory Limit:65536KB
Points:100
View Problem Statistics Submit Problem added debug

Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.

Input

Первая строка содержит заданный шаблон длиной не более 80 символов.

Output

Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2*109.

Sample

InputOutput
????(?2
View Problem Statistics Submit Problem discussion Author/source:
Sorted Problems / Dynamic programming, recurrent relations /
1066. Report 67. 834. Scheduling Lectures 2. Search tree 213. Squares
Problems from Contests and Camps / Trainings of Vologda SU / Dynamic Programmin /
70. Hacking of Network 67. 69. Spaces in Cube
Problems from Contests and Camps / VoSU Selection Rounds / VSPU Selection Round 2014 /
267. 5 - From Fly to Elefant 67.
Problems from Contests and Camps / School olympiads and couses of Vologda region / Impulse - 2019 / Final Olympiad /
296. 06 - Palindrom 67. 1265. 08 - Symmetry 859. 09 - How to Help Me 695. 10 - Near Numbers
time generating 0.109 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.