Counting Permutations by Segment MEX Conditions

Alice has a permutation a of length \( n \) containing all the integers \(0, 1, 2, \ldots, n-1\). Bob wants to guess the permutation, but Alice gives him a hint instead. For every pair \((l, r)\) with \(1 \le l \le r \le n\), define:

[ f(l,r)=\operatorname{mex}{a_l,a_{l+1},\ldots,a_r}, ]

where \( \operatorname{mex} \) (minimum excluded value) is defined as the smallest non-negative integer that does not appear in the multiset. Note that if the segment contains all of \(0,1,\ldots,n-1\) then \(\operatorname{mex}=n\). However, Alice only reveals information about segments whose \( \operatorname{mex} \) is strictly less than \( n \).

The hint is given as \( n \) numbers. The \( i\)th number (for \(i=1,2,\ldots,n\)) indicates the number of pairs \((l, r)\) for which \( f(l,r)= i-1 \). Bob realizes that these conditions do not uniquely determine the permutation. Now, he wonders: how many different permutations \(a\) of \(0,1,\ldots,n-1\) satisfy the given conditions?

Note: For a subarray \(a[l\dots r]\), if \(f(l,r)=n\) (which happens when the segment contains all numbers), then that segment is not counted in any of the provided conditions.

inputFormat

The first line contains an integer \( n \) (with small constraints, e.g. \( n \le 8 \)).

The second line contains \( n \) space‐separated integers \( b_0, b_1, \ldots, b_{n-1} \), where \( b_x \) represents the number of subarray pairs \((l,r)\) such that \( f(l, r)=x \).

outputFormat

Output a single integer representing the number of permutations of \(0,1,\ldots,n-1\) that satisfy the given segment \( \operatorname{mex} \) conditions.

sample

3
3 1 1

2