A. Einstein's Calculator
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Einstein has a calculator and a list of numbers that he wants to put into his calculator! More specifically, Einstein has an array $$$a$$$ of $$$n$$$ $$$(2 \leq n \leq 100)$$$ numbers that he will put into his calculator. And one of Einstein's favorite equations is $$$6 + 7 + 6 + 7 + 41 + 0 = 67$$$, so every number in $$$a$$$ is guaranteed to be one of $$${0, 6, 7, 41, 67}$$$.

Einstein wants to put an operator $$$+$$$, $$$-$$$, $$$/$$$, or $$$\cdot$$$ between each number in order to make a valid expression to put into the calculator. He also wants to maximize the value of the expression that he forms and ensure that it is not undefined (there is never $$$0/0$$$). Note that there is no limit on how many of any operator Einstein uses, and that he is allowed to use operators more than once.

If Einstein chooses the operators in his expression optimally, what is the maximum value of the expression that he can achieve? In other words, what is Einstein doing on that calculator? Because the value may be very large, print it modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 100)$$$ where $$$n$$$ the size of $$$a$$$.

The second line contains $$$n$$$ integers, $$$[a_1, a_2, ... a_n]$$$ ($$$a_i \in \{0, 6, 7, 41, 67\}$$$), the elements in $$$a$$$.

Output

Output one number, the maximum value of Einstein expression modulo $$$10^9 + 7$$$.

Example
Input
4
6 7 41 0
Output
1722
Note

In the sample test case, we need to fill in the operators for:

$$$6$$$ _ $$$7$$$ _ $$$41$$$ _ $$$0$$$

One possible way we can maximize the value of the expression is by assigning the operators as follows:

$$$6 \cdot 7 \cdot 41 - 0 = 1722$$$

It can be proven that 1722 is the maximum value that can be achieved.