2607 问题 H: 蓝桥杯2021年第十二届省赛真题-括号序列

时间限制: 1s 内存限制: 128MB 提交: 1581 解决: 201
题目描述
给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。
输入
输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和
右括号。
输出
输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007 (即109 + 7) 的余数。
样例输入
((()
样例输出
5
提示
【评测用例规模与约定】
对于 40% 的评测用例，|s| ≤ 200。
对于所有评测用例，1 ≤ |s| ≤ 5000。 

                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
1........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
                        

                    

                

                

                    

                        
比赛状况