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-----
Input:
2
1 2 3
3
3 1 5 2 6 4 7
0

Output:
3
105

Explanation:

The second test case is constructed as follows:

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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def treeProduct(num, h, root, ch):
	if ch >= h:
		return num[root]
	left = root * 2 + 1
	right = root * 2 + 2
	ret1 = treeProduct(num, h, left, ch + 1)
	ret2 = treeProduct(num, h, right, ch + 1)
	return num[root] * max(ret1, ret2)

def main():
	n = int(input())
	while n != 0:
		line = str(input())
		s = line.split()
		num = [int(e) for e in s]
		print(int(treeProduct(num, n, 0, 1) % 1000000007))
		n = int(input())

def __starting_point():
	main()
__starting_point()


a = []

def maxx(a, b):
	if a > b:
		return a
	return b

def fnd(cur, mx):
	if cur > mx:
		return 1
	f = fnd(2 * cur, mx)
	g = fnd(2 * cur + 1, mx)
	return a[cur] * maxx(f, g)

def main():
	while 1:
		n = eval(input())
		if n == 0:
			break
		while len(a) != 0:
			a.pop()
		a.append(0)
		x = input().split()
		mx = 2 ** n - 1
		for i in range(0, 2 ** n - 1):
			a.append(int(x[i]))
		print(fnd(1, mx) % 1000000007)
main()


import sys

def f(a, b, c, l, d):
	if a > l:
		return 1
	if b == c:
		return d[a]
	else:
		mid = (b + c) / 2
		id1 = f(2 * a, b, mid, l, d)
		id2 = f(2 * a + 1, mid + 1, c, l, d)
		id1 = id1 * d[a]
		id2 = id2 * d[a]
		if id1 > id2:
			return id1
		else:
			return id2
t = int(sys.stdin.readline())
while t:
	d = []
	d.append(0)
	x = sys.stdin.readline().split()
	l = len(x)
	for i in range(l):
		d.append(int(x[i]))
	ans = f(1, 1, (1 << t) - 1, (1 << t) - 1, d)
	ans = ans % 1000000007
	print(ans)
	t = int(sys.stdin.readline())


import sys
while 1:
	n = int(sys.stdin.readline().strip())
	if n == 0:
		return
	a = list(map(int, input().split()))
	for i in range(2 ** (n - 1) - 2, -1, -1):
		a[i] = max(a[i] * a[2 * (i + 1) - 1], a[i] * a[2 * i + 2])
	print(a[0] % 1000000007)


def main():
	while True:
		h = int(input())
		if h == 0:
			break
		lineproc = input().split()
		nodes = []
		nodes.append(int(lineproc[0]))
		for i in range(1, int(2 ** h) - 1):
			number = int(lineproc[i]) * nodes[int((i + 1) / 2) - 1]
			nodes.append(number)
		print(max(nodes) % 1000000007)
main()


while 1:
	N = eval(input())
	if N == 0:
		break
	A = list(map(int, input().split(' ')))
	for i in range(N - 1, 0, -1):
		C = 1 << i - 1
		B = 1 << i
		for j in range(C - 1, B - 1, 1):
			A[j] = A[j] * max(A[2 * j + 1], A[2 * j + 2])
	print(A[0] % 1000000007)


import sys
f = sys.stdin
while True:
	H = int(f.readline())
	if H == 0:
		break
	v = list(map(int, f.readline().split()))
	p = [0] * 2 ** H
	for i in range(2 ** H - 1, 0, -1):
		if i * 2 >= 2 ** H:
			p[i] = v[i - 1]
		else:
			p[i] = v[i - 1] * max(p[2 * i], p[2 * i + 1])
	r = p[1] % 1000000007
	print(r)


from math import ceil as ceil

def parent(index):
	return int(ceil(index / 2) - 1)
while True:
	length = int(input())
	if length == 0:
		break
	numbers = input().split()
	tree = [0] * len(numbers)
	for i in range(0, len(numbers)):
		tree[i] = int(numbers[i])
	lastIndex = len(tree) - 1
	if lastIndex & 1:
		tree[parent(lastIndex)] = tree[parent(lastIndex)] * tree[lastIndex]
		--lastIndex
	for i in range(lastIndex, 0, -2):
		parentIndex = parent(i)
		tree[parentIndex] = max(tree[parentIndex] * tree[i], tree[parentIndex] * tree[i - 1])
	print(tree[0] % 1000000007)


import math

def Left(i):
	return 2 * i

def Right(i):
	return 2 * i + 1

def levelOf(x):
	return int(math.floor(math.log10(x) / math.log10(2) + 1))

def treeProduct(numList, n, i):
	if levelOf(i) == n:
		return numList[i]
	else:
		tpl = treeProduct(numList, n, Left(i))
		tpr = treeProduct(numList, n, Right(i))
		if tpl > tpr:
			return numList[i] * tpl
		else:
			return numList[i] * tpr

def main():
	n = int(input())
	while n != 0:
		line = '-1 ' + str(input())
		s = line.split()
		num = [int(e) for e in s]
		print(int(treeProduct(num, n, 1) % 1000000007))
		n = int(input())

def __starting_point():
	main()
__starting_point()