{"raw_statement":[{"iden":"statement","content":"#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.\n\nLets 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).\n\nGiven 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.\n\nFirst line of the input contains one integer n — length of permutation (1 ≤ n ≤ 27, n = 2k + 1 for some integer k).\n\nSecond 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.\n\nPrint one integer — number of the extreme permutations where all fixed elements are on their positions.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"Print one integer — number of the extreme permutations where all fixed elements are on their positions."},{"iden":"examples","content":"Input50 0 0 0 0Output4Input50 1 0 0 5Output1"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ 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 $.  \nLet $ 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 $.  \nA 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\\} $:  \n$$\n|\\sigma_i - \\sigma_{i+1}| \\geq \\min(\\sigma_i, \\sigma_{i+1})\n$$\n\n**Constraints**  \n1. $ n $ is odd, $ 1 \\leq n \\leq 27 $.  \n2. For each $ i \\in \\{1, \\dots, n\\} $:  \n   - $ p_i = 0 $: position $ i $ is free.  \n   - $ p_i > 0 $: $ \\sigma_i = p_i $ (fixed).  \n3. All fixed values $ p_i > 0 $ are distinct.  \n\n**Objective**  \nCount the number of extreme permutations $ \\sigma $ of length $ n $ satisfying $ \\sigma_i = p_i $ for all $ i $ where $ p_i > 0 $.","simple_statement":"Given an odd number n, count the number of extreme permutations of length n where some positions are fixed.\n\nA permutation is extreme if for every two adjacent numbers, the absolute difference between them is at least the smaller of the two.\n\nInput:  \n- First line: odd integer n (1 ≤ n ≤ 27)  \n- Second line: n integers, where 0 means not fixed, and a positive number means that position must contain that number  \n\nOutput:  \n- The number of extreme permutations satisfying the fixed positions.","has_page_source":false}