Migrated from Lutece 1643 括号匹配

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一个仅包含$'('$和$'?'$的括号序列，你需要把每个$'?'$替换为$'('$或$')'$
请问有多少种替换方法，使得最后的括号序列是一个合法括号序列?
答案可能很大，请输出模$4294967296$后的答案

Input

输入一个字符串，长度不超过$100000$

Output

输出模$4294967296$后方案数

Samples

(???

2

Resources

missever