SP2565 PERMUT3 - Another Permutation Problem

Given a permutation of **n** elements (1, 2, ..., n): A = (a $ _{1} $ , a $ _{2} $ , ..., a $ _{n} $ ). We define a sequence P(A)=(p $ _{1} $ , p $ _{2} $ , …, p $ _{n-1} $ ) where p $ _{i} $ = 0 if a $ _{i} $ > a $ _{i+1} $ and p $ _{i} $ = 1 if a $ _{i} $ < a $ _{i+1} $ . Given a permutation B, find the number of all permutations C where P(C)=P(B) including the permutation B itself. **The length of your solution should not be more than 0.5kB.**

Multiple test cases. For each test case: The first line contains an integer **n**(1

For each test case: The output contains a single line with a single integer - the number of the permutations having the same value for P(A) when given the permutation A.