CF1776N.Count Permutations

You are given a string $s$ with length $n-1$ whose characters are either \texttt{ \lt } or \texttt{ \gt }.

Count the permutations $p_1, \, p_2, \, \dots, \, p_n$ of $1, \, 2, \, \dots, \, n$ such that, for all $i = 1, \, 2, \, \dots, \, n - 1$, if $s_i$ is \texttt{ \lt } then $p_i \lt p_{i+1}$ and if $s_i$ is \texttt{ \gt } then $p_i \gt p_{i+1}$.

Since this number can be very large, compute its logarithm in base $2$.

给你一个长度为 $n-1$ 的字符串 $s$，其每个字符均为 \texttt{ \lt } 或 \texttt{ \gt }。

统计 $1, \, 2, \, \dots, \, n$ 的排列 $p_1, \, p_2, \, \dots, \, p_n$ 的个数，使得对所有 $i = 1, \, 2, \, \dots, \, n - 1$，若 s_i = \texttt{ \lt }，则 $p_i \lt p_{i+1}$；若 s_i = \texttt{ \gt }，则 $p_i \gt p_{i+1}$。

由于该数目可能非常大，请计算其以 $2$ 为底的对数。

The first line contains a single integer $n$ ($2 \le n \le 100\,000$).

The second line contains a string $s$ of length $n-1$; each character of $s$ is either \texttt{ \lt } or \texttt{ \gt }.

第一行包含一个整数 $n$（$2 \le n \le 100\,000$）。

第二行包含一个长度为 $n-1$ 的字符串 $s$；$s$ 中的每个字符均为 \texttt{ \lt } 或 \texttt{ \gt }。

Print the logarithm in base $2$ of the number of permutations satisfying the constraints described in the statement.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$. Formally, let your answer be $x$ and let the correct answer be $y$. Your answer is accepted if and only if $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$.

输出满足题目描述中约束条件的排列数量以 $2$ 为底的对数。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。形式化地说，设你的答案为 $x$，正确答案为 $y$，当且仅当 $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-6}$ 时，你的答案被接受。

In the first sample, there is only one valid permutation, that is $[2, 1]$. Since $\log_2(1)=0$, the correct output is $0$.

In the second sample, there are $2$ valid permutations, that are $[3, 1, 2]$ and $[2, 1, 3]$. Since $\log_2(2)=1$, the correct output is $1$.

In the third sample, there are $4$ valid permutations, that are $[1, 5, 4, 3, 2]$, $[2, 5, 4, 3, 1]$, $[3, 5, 4, 2, 1]$, $[4, 5, 3, 2, 1]$. Since $\log_2(4)=2$, the correct output is $2$.

In the fourth sample, there are $909$ valid permutations. Notice that $\log_2(909)=9.828136484194\ldots$

在第一个样例中，仅存在一个有效的排列，即 $[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$