Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

• Any left parenthesis '(' must have a corresponding right parenthesis ')'
• Any right parenthesis ')' must have a corresponding left parenthesis '('
• Left parenthesis '(' must go before the corresponding right parenthesis ')'
• '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string ""

Examples

Example 1

Input:  s = "()"
Output: 1

The string is valid with balanced parentheses

Example 2

Input:  s = "(*)"
Output: 1

The * can be treated as ), making it valid

Example 3

Input:  s = "(*))"
Output: 1

One way is (* becomes (), then we have ())

Example 4

Input:  s = "(()"
Output: 0

Not enough closing parentheses

Constraints

• 1 <= s.length <= 100
• s[i] is '(', ')' or '*'