Minimum Final Value and Lexicographically Smallest Operation Sequence

You are given an initial sequence \(a_1, a_2, \ldots, a_n\) of length \(n\) which only contains the values \(0, 1, 2\). You can perform the following operation repeatedly:

• Choose two adjacent positions \(j\) and \(j+1\); remove \(a_j\) and \(a_{j+1}\) and insert in their place \(\mathrm{popc}(a_j+a_{j+1})\). The rest of the sequence shifts left by one position. Here, \(\mathrm{popc}(x)\) denotes the number of \(1\)'s in the binary representation of \(x\), i.e.: \[ \mathrm{popc}(x)=\begin{cases} 0, & x=0,\\ 1, & x=1,2,4,\ldots,\\ 2, & x=3,7,\ldots \end{cases} \] In our case, since \(a_i\in\{0,1,2\}\), note that for any two adjacent numbers:
  \(\mathrm{popc}(0+0)=0\),
  \(\mathrm{popc}(0+1)=\mathrm{popc}(1+0)=\mathrm{popc}(0+2)=\mathrm{popc}(2+0)=1\),
  \(\mathrm{popc}(1+1)=1\),
  \(\mathrm{popc}(1+2)=\mathrm{popc}(2+1)=2\),
  \(\mathrm{popc}(2+2)=1\).

After each operation the sequence length decreases by \(1\). After exactly \(n-1\) operations, only one number remains. Let \(t\) be the smallest possible final value over all valid sequences of \(n-1\) operations. An operation sequence \(p\) is an array of \(n-1\) positive integers where \(p_i\) represents the chosen index \(j\) in the \(i\)th operation (note that after every operation, the positions are renumbered from \(1\) to the current sequence length). A sequence \(p\) is considered good if performing the operations in order yields the final number \(t\). Among all good operation sequences, you are to find the lexicographically smallest one.

Since the output sequence might be huge, instead of printing the sequence itself, you are required to output its hash value computed as follows:

hash = 0
for each number x in the operation sequence:
    hash = (hash * 131 + x) mod 1000000007

If you cannot compute the lexicographically smallest good operation sequence, you can still obtain partial points (see scoring details).

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le 10\)).
The second line contains \(n\) space-separated integers representing the sequence \(a_1, a_2, \ldots, a_n\). It is guaranteed that each \(a_i\) is either \(0\), \(1\), or \(2\).

outputFormat

Output a single integer: the hash value of the lexicographically smallest good operation sequence computed as described.

sample

2
0 1

1