给定一个字符串 $$$s$$$,长度为 $$$n-1$$$,其字符为 $$$\texttt{<}$$$ 或 $$$\texttt{>}$$$。
计算 $$$1, \, 2, \, \dots, \, n$$$ 的排列 $$$p_1, \, p_2, \, \dots, \, p_n$$$ 使得对于所有 $$$i = 1, \, 2, \, \dots, \, n - 1$$$,如果 $$$s_i$$$ 是$$$\texttt{<}$$$ 则 $$$p_i < p_{i+1}$$$ 并且如果 $$$s_i$$$ 为 $$$\texttt{>}$$$ 则 $$$p_i > p_{i+1}$$$。
由于这个数字可能非常大,请计算其以 $$$2$$$ 为底的对数。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100\,000$$$)。
第二行包含长度为$$$n-1$$$的字符串$$$s$$$; $$$s$$$ 的每个字符都是 $$$\texttt{<}$$$ 或 $$$\texttt{>}$$$。
输出
打印满足语句中描述的约束的排列数的以 $$$2$$$ 为底的对数。
如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。正式来说,让您的答案为 $$$x$$$,正确答案为 $$$y$$$。当且仅当 $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入 #1
2 <
输出 #1
0.0000000000
输入 #2
3 <>
输出 #2
1.0000000000
输入 #3
5 ><<<
输出 #3
2.0000000000
输入#4
10 <><<<<<>>
输出#4
9.8281364842
注意
在第一个样本中,只有一个有效排列,即 $$$[2, 1]$$$。由于$$$\log_2(1)=0$$$,正确的输出是$$$0$$$。
在第二个样本中,有 $$$2$$$ 有效排列,即 $$$[3, 1, 2]$$$ 和 $$$[2, 1, 3]$$$。由于$$$\log_2(2)=1$$$,正确的输出是$$$1$$$。
在第三个样本中,有 $$$4$$$ 有效排列,即 $$$[1, 5, 4, 3, 2]$$$, $$$[2, 5, 4, 3, 1]$$$, $$$[3, 5, 4, 2, 1]$$$, $$$[4, 5, 3, 2, 1]$$$。由于$$$\log_2(4)=2$$$,正确的输出是$$$2$$$。
在第四个样本中,有 $$$909$$$ 有效排列。请注意 $$$\log_2(909)=9.828136484194\ldots$$$