Count Valid Bracket Sequences

You are given a string s of length n consisting of the characters (', ')', '[', ']', '{', '}' and '?'. The character '?' represents an unknown bracket. Your task is to count the number of ways to replace each '?' with one of the six bracket characters so that the final string becomes a valid bracket sequence.

A valid bracket sequence is defined by the following rules:

• The empty string is a valid bracket sequence.
• If A is a valid bracket sequence, then (A), [A] and {A} are also valid bracket sequences.
• If A and B are valid bracket sequences, then the concatenation AB is also a valid bracket sequence.

Note: When replacing '?', you must pick one of the six bracket characters. In order for a pair of characters at positions i and j to form a matching pair, they must either be exactly (' and ')', '[' and ']', or '{' and '}'. If one or both of these characters is a '?', it can be replaced by the corresponding bracket needed for the matching pair.

Your answer should be the total number of ways to achieve a valid bracket sequence. If it is impossible, output 0.

Hint: You may solve this problem using dynamic programming. Consider using a DP recurrence formula of the form:

$$dp[i][j]=\sum_{k=i+1 \atop k-i\;\text{is odd}}^{j}\big(\text{match}(s_i,s_k)\cdot dp[i+1][k-1]\cdot dp[k+1][j]\big), $$

where match(a,b) returns the number of ways to choose a matching pair for the characters a and b (taking into account '?').

inputFormat

The input consists of a single line that contains a string s of length n (possibly containing the character '?').

outputFormat

Output a single integer: the number of ways to replace each '?' so that the string becomes a valid bracket sequence.

sample

()

1