有四种类型的括号：圆括号 ()、方括号 []、花括号 {} 和尖括号 <>。括号序列的合法性定义如下：

Photo by Tomek Niedzwiedz

• 空序列是合法的。
• 如果 $X$ 是一个合法的括号序列，则 $pXq$ 也是一个合法的括号序列，其中 $p$ 是左括号，$q$ 是右括号，且 $p$ 和 $q$ 类型相同。
• 如果 $X$ 和 $Y$ 是合法的括号序列，则它们的拼接 $Z = XY$ 也是一个合法的括号序列。

你拥有一个括号序列，其中一些括号是已知的，而另一些是未知的，用问号（?）表示。你需要使用上述四种类型的括号填补每一个未知括号，以得到一个合法的括号序列。请问你能得到多少种不同的合法括号序列？

输入格式

输入包含一行，给出一个非空的括号序列。序列长度为偶数且不超过 20。序列中的所有字符要么是四种类型的左括号或右括号之一，要么是表示未知括号的问号。序列中至少包含一个问号。

输出格式

输出你能得到的不同合法括号序列的数量。

样例

输入格式 1

(??)

输出格式 1

5

输入格式 2

(<{}>??]

输出格式 2

1

输入格式 3

(?]]

输出格式 3

0