github.com/captn3m0/codechef.git

---
languages_supported:
    - NA
title: TPRODUCT
category: NA
old_version: true
problem_code: TPRODUCT
tags:
    - NA
layout: problem
---
###  All submissions for this problem are available. 

Given a complete binary tree with the height of H, we index the nodes respectively top-down and left-right from 1. The i-th node stores a positive integer Vi. Define Pi as follows: Pi=Vi if the i-th node is a leaf, otherwise Pi=max(Vi\*PL, Vi\*PR), where L and R are the indices of the left and right children of i, respectively. Your task is to caculate the value of P1.

### Input

There are several test cases (fifteen at most), each formed as follows:

- The first line contains a positive integer H (H ≤ 15).
- The second line contains 2H-1 positive integers (each having a value of 109 at most), the i-th integer shows the value of Vi.

The input is ended with H = 0. ### Output

For each test case, output on a line an integer which is the respective value of P1 found, by modulo of 1,000,000,007.

### Example

<pre>
<b>Input:</b>
2
1 2 3
3
3 1 5 2 6 4 7
0

<b>Output:</b>
3
105

</pre>Explanation:
The second test case is constructed as follows: ```

     3
    / \
   /   \
  1     5
 / \   / \
2   6 4   7

<pre>