Balanced Braces

You are given a string \(S\) consisting only of the characters '{' and '}'. Your task is to determine whether the braces in \(S\) are properly balanced. A string is said to have balanced braces if:

[ \text{For every prefix of the string, the number of '{' is no less than the number of '}' and the total counts of '{' and '}' are equal.} ]

If the braces are balanced, print 1; otherwise, print 0. Note that the input can be very large (up to tens of thousands of characters) so your solution should be efficient.

Examples:

• Input: {{{}}} → Output: 1
• Input: {{{}} → Output: 0
• Input: {}{} → Output: 1
• Input: }{ → Output: 0

inputFormat

The input consists of a single line containing the string (S), which is a sequence of the characters '{' and '}'. The string may be empty.

outputFormat

Output a single integer: 1 if the braces in the input string (S) are balanced, or 0 otherwise.## sample

{{{}}}

1