|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||1536 MB||0||0||0||0.000%|
Do you know Just Odd Inventions Co., Ltd.? The business of this company is doing “just odd inventions.” Here we just call it JOI Company.
There is a security gate installed in the doorway of JOI Company, in order to prevent confidential information leaks. One must pass through the gate when entering or exiting the company. It is impossible for two or more people to pass through the gate at the same time.
Whenever a person pass through this gate, it records the information indicating that a person enters or exits the company. Now, IOI-kun, an employee of JOI Company, has a record of the gate for some day. The record is represented by string S : if the i-th character of S is ‘(’, it means that the i-th person who passed through the gate entered the company, and if the i-th character of S is ‘)’, it means that the i-th person who passed through the gate exited the company. IOI-kun knows that there were no people inside JOI Company at the beginning or at the end of this day. Note that there exist strings consisting only of ‘(’ and ‘)’ which cannot represent a record: for example, a record cannot be ())( or (() because it would follow that the number of people inside JOI Company had become negative or there had been a person inside JOI Company at the end of the day, respectively.
The next moment IOI-kun checked the record, the string S was modified by a computer virus spread across JOI Company! After some investigation, he supposed that the modification took the following process:
IOI-kun does not remember S , so he tries to recover S from S′′. For that, he wants first to count the number of strings which can be S′ (not S , be careful).
Given string S′′, write a program which calculates the number of strings which can be S′, modulo 1 000 000 007.
Read the following data from the standard input.
Write one line to the standard output. The output should contain the number of strings which can be S′, modulo 1 000 000 007. If there is no such string, output 0.
In Sample Input 1, S′ = )))( is not possible because there is no string which can be S . The following three strings can be S′:
Since only these strings can be S′, output 3.