You are given a string s consisting of characters: (, ), [, ], { and }. Write a program to check whether the characters in the string s are valid or not.

Problem Note:

• A string if said to be valid if an open parenthesis is closed by the same type of parenthesis.
• Also, the open parenthesis must be closed in the correct order.
• Return 1, if the string is valid, else return 0.

Example 1

Input: "(([](){}))"
Output: 1
Explanation: In the above example, every parenthesis and bracket has opening and closing in the correct order. Thus, we get 1(true) as output.

Example 2

Input: "([)]"
Output: 0
Explanation: In the above example, the brackets are closed but not in the correct order. Thus, we get 0(false) as output.

Example 3

Input: "()[]({})"
Output: 1
Explanation: In the above example, every parenthesis and bracket has opening and closing in the correct order. Thus, we get 1(true) as output.