#cf_span(class=[tex-font-style-underline], body=[Permutation]) of length n is called the sequence of n integers, containing each of integers between 1 and n exactly once. For example, (3, 4, 5, 1, 2) and (1, 2) are permutations, (1, 4, 3) and (2, 1, 3, 2) are not.
Lets call the permutation #cf_span(class=[tex-font-style-underline], body=[extreme]), if for any two neighbor numbers in the permutation difference between them is not less than minimum of those 2 numbers. For example, permutation (3, 1, 2, 4) is extreme, because |3 - 1| ≥ min(3, 1), |1 - 2| ≥ min(1, 2) and |2 - 4| ≥ min(2, 4).
Given an #cf_span(class=[tex-font-style-underline], body=[odd]) n, calculate number of the extreme permutations of length n where positions of some integers are fixed.
First line of the input contains one integer n — length of permutation (1 ≤ n ≤ 27, n = 2k + 1 for some integer k).
Second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ n). If pi is equal to 0, then i-th position is not fixed, otherwise on i-th position must stay pi. You may assume that if pi > 0 and pj > 0 for 1 ≤ i, j ≤ n, i ≠ j, then pi ≠ pj.
Print one integer — number of the extreme permutations where all fixed elements are on their positions.
## Input
First line of the input contains one integer n — length of permutation (1 ≤ n ≤ 27, n = 2k + 1 for some integer k).Second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ n). If pi is equal to 0, then i-th position is not fixed, otherwise on i-th position must stay pi. You may assume that if pi > 0 and pj > 0 for 1 ≤ i, j ≤ n, i ≠ j, then pi ≠ pj.
## Output
Print one integer — number of the extreme permutations where all fixed elements are on their positions.
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be an odd integer such that $ n = 2k + 1 $ for some $ k \in \mathbb{Z}_{\geq 0} $, and $ 1 \leq n \leq 27 $.
Let $ P = (p_1, p_2, \dots, p_n) $ be a partial permutation where $ p_i \in \{0\} \cup \{1, 2, \dots, n\} $, and if $ p_i > 0 $ and $ p_j > 0 $ for $ i \neq j $, then $ p_i \neq p_j $.
A full permutation $ \sigma = (\sigma_1, \sigma_2, \dots, \sigma_n) $ of $ \{1, 2, \dots, n\} $ is called **extreme** if for all $ i \in \{1, 2, \dots, n-1\} $:
$$
|\sigma_i - \sigma_{i+1}| \geq \min(\sigma_i, \sigma_{i+1})
$$
**Constraints**
1. $ n $ is odd, $ 1 \leq n \leq 27 $.
2. For each $ i \in \{1, \dots, n\} $:
- $ p_i = 0 $: position $ i $ is free.
- $ p_i > 0 $: $ \sigma_i = p_i $ (fixed).
3. All fixed values $ p_i > 0 $ are distinct.
**Objective**
Count the number of extreme permutations $ \sigma $ of length $ n $ satisfying $ \sigma_i = p_i $ for all $ i $ where $ p_i > 0 $.