22798번 - Permutation 다국어

문제

Given a permutation of n elements (1, 2, ..., n): A = (a₁, a₂, . . . , a_n). We define a sequence P(A) = (p₁, p₂, . . . , 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 input text file contains several tests, each on a separate line. The first number in the test is n (0 < n ≤ 1024) followed by n numbers representing the permutation all of them separated by a single space. The last line in the input contains only 0 and should not be processed.

출력

The output should be written on the standard output. For each line in the input (excluding the last one, 0) you should write the result i.e. the number of the permutations having the same value for P(A) when given the permutation A.

You may assume the result is less than 2³².

제한

힌트