CF1776N Count Permutations

You are given a string $ s $ with length $ n-1 $ whose characters are either $ \texttt{} $ . 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{} $ then $ p_i > p_{i+1} $ . Since this number can be very large, compute its logarithm in base $ 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{} $ .

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} $ .

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 $