Dude, you still have two lives
Don loves correctly parenthesized strings, your friend Raul loves sequences, and you love number theory. Don asked you to write a problem that meets the quality of the RoAlgo contest problems and to give a solution to this problem. You decided to combine number theory, correctly parenthesized strings, and sequences into a single problem.
A string is called correctly parenthesized if and only if you can insert the characters and such that the resulting string represents a correct mathematical expression. For example, and are correctly parenthesized strings because and are correct mathematical expressions, but and are not correctly parenthesized strings.
Task
You are given the number and a string of characters belonging to the set of length .
Find
Input data
The first line will contain a single natural number representing the number .
The second line contains a string of characters representing the string .
Output data
Output a single natural number representing the answer to the task.
Constraints and clarifications
- is the greatest common divisor of the numbers and .
- is if the subsequence is correctly parenthesized, otherwise it is
# | Points | Constraints |
---|---|---|
1 | 6 | |
2 | 11 | |
3 | 65 | |
4 | 18 | No other constraints |
Example
stdin
10
()()((()))
stdout
14
Explanation
The subsequences with are:
The subsequence with is:
The subsequence with is:
Therefore, the answer is .