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 V_{i}. Define P_{i} as follows: P_{i}=V_{i} if the i-th node is a leaf, otherwise P_{i}=max(V_{i}*P_{L}, V_{i}*P_{R}), where L and R are the indices of the left and right children of i, respectively. Your task is to caculate the value of P_{1}.

------ 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 2^{H}-1 positive integers (each having a value of 10^{9} at most), the i-th integer shows the value of V_{i}.

The input is ended with H = 0.

------ Output ------ 

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

----- Sample Input 1 ------ 
2
1 2 3
3
3 1 5 2 6 4 7
0
----- Sample Output 1 ------ 
3
105
----- explanation 1 ------ 
The second test case is constructed as follows:

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

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
def maxProduct(data, currentHeight):
	index = 0
	while index != len(data):
		nextDepth = list()
		for node in currentHeight:
			nextDepth.append(node * data[index])
			nextDepth.append(node * data[index + 1])
			index += 2
		currentHeight = nextDepth
	return max(currentHeight)
while True:
	if input() == '0':
		break
	data = [int(n) for n in input().split()]
	root = [data.pop(0)]
	print(maxProduct(data, root) % 1000000007)


while True:
	h = int(input())
	if h == 0:
		break
	nums = list(map(int, input().split(' ')))
	n = 2 ** h - 1
	p = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		if 2 * i + 1 >= n:
			p[i] = nums[i]
		else:
			p[i] = nums[i] * max(p[2 * i + 1], p[2 * i + 2])
	print(p[0] % 1000000007)


def maxProduct(data, fringe, H):
	for i in range(H - 1):
		nextDepth = list()
		for node in fringe:
			nextDepth.append(node * next(data))
			nextDepth.append(node * next(data))
		fringe = nextDepth
	return max(fringe)
while True:
	H = int(input())
	if H == 0:
		break
	data = iter(map(int, input().split()))
	print(maxProduct(data, [next(data)], H) % 1000000007)


MOD = 10 ** 9 + 7
h = int(input())
while h != 0:
	a = [int(i) for i in input().split()]
	for i in range(len(a) - 1, -1, -2):
		par = i // 2 - 1
		if par > 0:
			a[par] = max(a[par * 2 + 1] * a[par], a[par * 2 + 2] * a[par])
	print(max(a[1] * a[0], a[2] * a[0]) % MOD)
	h = int(input())


while True:
	n = int(input())
	if n == 0:
		break
	L = list(map(int, input().split()))
	i = n - 1
	while i > 0:
		if i >= 2:
			for j in range(2 ** i - 2, 2 ** (i - 1) - 2, -1):
				L[j] *= max(L[-1], L[-2])
				L.pop()
				L.pop()
		else:
			L[0] *= max(L[1], L[2])
		i -= 1
	print(L[0] % (10 ** 9 + 7))


from typing import List
from collections import deque
mod = 1000000007

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def build_tree(arr: List[int]) -> Node:
	n = len(arr)
	root = Node(arr[0])
	queue = deque([root])
	ind = 1
	while ind < n:
		cur = queue.popleft()
		cur.left = Node(arr[ind])
		queue.append(cur.left)
		cur.right = Node(arr[ind + 1])
		queue.append(cur.right)
		ind += 2
	return root

def postorder(root: Node) -> None:
	if root:
		left = postorder(root.left)
		right = postorder(root.right)
		root.data *= max(left, right)
		return root.data
	else:
		return 1

def soln(n: int, arr: List[int]) -> int:
	root = build_tree(arr)
	postorder(root)
	return root.data % mod
while True:
	n = int(input())
	if n > 0:
		arr = list(map(int, input().split()))
		print(soln(n, arr))
	else:
		break


z = 0
while z == 0:
	h = int(input())
	if h == 0:
		break
	n = (1 << h) - 1
	p = [0] * (n + 10)
	v = [int(x) for x in input().split()]
	for i in range(n - 1, -1, -1):
		if 2 * i + 1 >= n:
			p[i] = v[i]
		else:
			p[i] = v[i] * max(p[2 * i + 1], p[2 * i + 2])
	ans = p[0] % 1000000007
	print(ans)


from heapq import heapify, heappush, heappop
from cmath import pi
from distutils import extension
from pickle import FALSE
import sys
from math import gcd, sqrt, log10, log2, floor, ceil
from collections import deque, defaultdict
from tkinter.tix import Tree
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000007

def treePrd(arr, i):
	if 2 * i > len(arr):
		return arr[i - 1]
	return arr[i - 1] % mod * max(treePrd(arr, 2 * i), treePrd(arr, 2 * i + 1))
while True:
	h = ii()
	if h == 0:
		break
	arr = il()
	print(treePrd(arr, 1) % mod)


from sys import *
import math
from collections import Counter
mod = 1000000000 + 7
for _ in range(15):
	n = int(input())
	if n == 0:
		break
	lst = list(map(int, input().split()))
	if n == 1:
		print(lst[0])
		break
	index = len(lst) - 1
	leaf_nodes = index - 2 ** (n - 1) + 2
	ans = [0] * (index + 1)
	while index != 0:
		last = lst.pop()
		if leaf_nodes > 0:
			ans[index] = last
			leaf_nodes -= 1
		p_index = (index - 1) // 2
		ans[p_index] = max(ans[p_index], lst[p_index] * ans[index])
		index -= 1
	print(ans[0] % mod)


h = int(input())
while h != 0:
	vs = [0] + list(map(int, input().split()))
	for i in range(h - 1, 0, -1):
		st = 2 ** (i - 1)
		end = 2 ** i - 1
		for j in range(st, end + 1):
			vs[j] = vs[j] * max(vs[j * 2], vs[j * 2 + 1])
	print(vs[1] % 1000000007)
	h = int(input())


def makeAdj(arr):
	n = len(arr)
	adj = {i: [] for i in range(n)}
	for i in range(n):
		if 2 * i + 2 < n:
			adj[i].append(2 * i + 1)
			adj[i].append(2 * i + 2)
			adj[2 * i + 1].append(i)
			adj[2 * i + 2].append(i)
		elif 2 * i + 1 < n:
			adj[i].append(2 * i + 1)
			adj[2 * i + 1].append(i)
	return adj

def dfs(node, par, arr, adj, P):
	if len(adj[node]) == 1:
		P[node] = arr[node]
		return
	for child in adj[node]:
		if child == par:
			continue
		dfs(child, node, arr, adj, P)
		P[node] = max(P[child] * arr[node], P[node])
	return P
while True:
	h = int(input())
	if h == 0:
		break
	arr = list(map(int, input().split()))
	adj = makeAdj(arr)
	P = [0] * len(arr)
	print(dfs(0, -1, arr, adj, P)[0] % 1000000007)


n = int(input())
while n != 0:
	a = list(map(int, input().split()))
	for i in range(len(a) // 2 - 1, -1, -1):
		a[i] = max(a[i * 2 + 1] * a[i], a[i * 2 + 2] * a[i])
	print(a[0] % 1000000007)
	n = int(input())


import array as arr

def calc(a, n, i):
	if 2 * i >= n:
		return a[i]
	left = calc(a, n, 2 * i)
	right = calc(a, n, 2 * i + 1)
	m = max(left, right)
	return a[i] * m
n = int(input())
while n != 0:
	a = arr.array('i', [int(x) for x in input().split()])
	n = 2 ** n
	a.insert(0, 0)
	b = calc(a, n, 1)
	print(b % 1000000007)
	n = int(input())


from sys import *
mod = 1000000000 + 7

def solve():
	lst = list(map(int, input().strip().split(' ')))
	if n == 1:
		print(lst[0])
		return
	index = len(lst) - 1
	leaf_nodes = index - 2 ** (n - 1) + 2
	ans = [0] * (index + 1)
	while index != 0:
		last = lst.pop()
		if leaf_nodes > 0:
			ans[index] = last
			leaf_nodes -= 1
		p_index = (index - 1) // 2
		ans[p_index] = max(ans[p_index], lst[p_index] * ans[index])
		index -= 1
	print(ans[0] % mod)
for _ in range(15):
	n = int(input().strip())
	if n == 0:
		break
	solve()


mdl = 1000000007
while True:
	h = int(input())
	if h == 0:
		break
	n = 2 ** h - 1
	z = input().split()
	t = [0] + list(map(int, z[:n]))
	for ix in range(n // 2, 0, -1):
		ixc = 2 * ix
		t[ix] *= max(t[ixc], t[ixc + 1])
	print(t[1] % mdl)


a = 1000000007
while True:
	N = int(input())
	if N == 0:
		break
	v = list(map(int, input().split()))
	len = (1 << N) - 1
	for i in range(len // 2, -1, -1):
		left = i * 2 + 1
		right = i * 2 + 2
		if left < len and right < len:
			v[i] = v[i] * max(v[left], v[right])
		elif left < len:
			v[i] = v[i] * v[left]
	print(v[0] % a)


mod = 1000000007

def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
import sys
from collections import Counter

def main():
	if h == 1:
		print(lst[0])
		return
	index = len(lst) - 1
	leaf_nodes = index - 2 ** (h - 1) + 2
	ans = [0] * (index + 1)
	while index != 0:
		last = lst.pop()
		if leaf_nodes > 0:
			ans[index] = last
			leaf_nodes -= 1
		p_index = (index - 1) // 2
		ans[p_index] = max(ans[p_index], lst[p_index] * ans[index])
		index -= 1
	print(ans[0] % mod)
for _ in range(15):
	h = int(input())
	if h == 0:
		break
	lst = integer_list()
	main()


while True:
	h = int(input())
	if h == 0:
		break
	vi = list(map(int, input().split()))
	lenl = (1 << h) - 1
	for i in range(lenl // 2, -1, -1):
		lind = i * 2 + 1
		rind = i * 2 + 2
		if lind < lenl and rind < lenl:
			vi[i] = vi[i] * max(vi[lind], vi[rind])
		elif lind < lenl:
			vi[i] = vi[i] * vi[lind]
	print(vi[0] % 1000000007)


z = 0
while z == 0:
	h = int(input())
	if h == 0:
		break
	n = 2 ** h - 1
	p = [0] * (n + 10)
	v = list(map(int, input().split()))
	for i in range(n - 1, -1, -1):
		if 2 * i + 1 >= n:
			p[i] = v[i]
		else:
			p[i] = v[i] * max(p[2 * i + 1], p[2 * i + 2])
	ans = p[0] % (1000000000 + 7)
	print(ans)


i = int(input())
modu = 1000000007
while i != 0:
	tree = [int(i) for i in input().split()]

	def P(ind):
		l = 2 * ind + 1
		r = 2 * ind + 2
		if l >= len(tree):
			return tree[ind]
		else:
			return tree[ind] * max(P(l), P(r))
	print(P(0) % modu)
	i = int(input())


h = int(input())
while h != 0:
	l = list(map(int, input().split()))
	i = len(l)
	f = 1
	c = 10 ** 9 + 7
	prev = 10000000112121121
	while i >= 1 and f == 1:
		x = i // 2
		if x < prev:
			max = 0
			prev = x
		calv = l[i - 1] * l[x - 1]
		if calv > max:
			max = calv
		if i % 2 == 0:
			l[x - 1] = max
		i = i - 1
	print(l[0] % c)
	h = int(input())


from math import log2
MOD = 10 ** 9 + 7

def solve(V, H):
	logV = [log2(i) for i in V]
	N = 2 ** H - 1
	for i in range(0, N // 2):
		(left, right) = (2 * i + 1, 2 * i + 2)
		V[left] = V[i] * V[left] % MOD
		V[right] = V[i] * V[right] % MOD
		logV[left] += logV[i]
		logV[right] += logV[i]
	(maxLog, ans) = (0.0, 0)
	for i in range(N // 2, N):
		if logV[i] > maxLog:
			maxLog = logV[i]
			ans = V[i]
	print(ans)
while True:
	H = int(input())
	if H == 0:
		break
	V = list(map(int, input().split()))
	solve(V, H)


solver = 1
sol = []

def callup(s, solver):
	if s == 1 or s == 0:
		k = l[1] * solver
		sol.append(k)
	else:
		solver = l[s] * solver
		s = s // 2
		callup(s, solver)
while True:
	n = int(input())
	if n == 0:
		break
	l = list(map(int, input().split()))
	l.insert(0, 0)
	for i in range(len(l) - 1, 0, -1):
		l[i] = callup(i, solver)
		solver = 1
	print(max(sol) % 1000000007)
	sol = []
	solver = 1