Regular bracket sequence - MarisaOJ: Marisa Online Judge

You are given a incompleted bracket sequence

S

$S$ consists of 3 types of characters

(

$($ ,

)

$)$ and

?

$?$ . Count the number of way to replace

?

$?$ with either

(

$($ or

)

$)$ to obtain a regular bracket sequence (RBS). Definition of RBS: - A string of length

0

$0$ is an RBS. - If

A

$A$ is an RBS, then

(A)

$(A)$ is also an RBS. - If

A

$A$ and

B

$B$ are RBS, then

A B

$AB$ is also an RBS. ### Input - The first line contains the string

S

$S$ . ### Output - Print one integer, the number of ways modulo

10^{9} + 7

$10^9+7$ . ### Constraints -

1 \leq | S | \leq 1000

$1 \le |S| \le 1000$ . ### Example Input:

(? ? ?

$(???$

Output:

2

$2$

#### Note: There are 2 RBSs

() ()

$()()$ and

(())

$(())$ .

Introduction to Dynamic Programming (Part two)
	Sake game
	Coins
	Coins 2
	Game on array
	Longest increasing subsequence 2
	Convolution
	Regular bracket sequence
	Faulty addition
	Weird bank
	Delete operation
	Palindromize
	Color ribbon
	Unique subsequences
	Unique subsequences 2
	Cow exhibition
	Knapsack 3
	Compressing array
	Regular bracket sequence 2
	Maximum path 3
	Concating substring
	Soil
	Stacking boxes
	String transformation
	Palindromic quadruple
	Finding teammates

Topic

Dynamic Programming

Rating

1200

Solution (0)

Solution