Cho số nguyên ~M~ và mảng ~f~ gồm ~2^M~ phần tử, đánh chỉ số từ ~0~ đến ~2^M - 1~.

Với mỗi ~i~ (~0 \le i < 2^M~), hãy tính: $$g[i] = \sum_{j \subseteq i} f[j] \pmod{10^9 + 7}$$

trong đó ~j \subseteq i~ nghĩa là ~j~ là một mặt nạ bit con (submask) của ~i~, tức là mọi bit ~1~ của ~j~ đều là bit ~1~ của ~i~.

Input

• Dòng đầu là số nguyên ~M~ (~1 \le M \le 20~).
• Dòng thứ hai gồm ~2^M~ số nguyên ~f[0], f[1], \ldots, f[2^M - 1]~ (~0 \le f[i] \le 10^6~).

Output

In ra ~2^M~ số nguyên trên một dòng, cách nhau bởi dấu cách, là các giá trị ~g[0], g[1], \ldots, g[2^M - 1]~.

Ví dụ

Input

2
1 2 3 4

Output

1 3 4 10

Giải thích

• ~g[0] = f[0] = 1~ (submask của ~00_2~ chỉ có ~00_2~)
• ~g[1] = f[0] + f[1] = 1 + 2 = 3~ (submask của ~01_2~ là ~00_2, 01_2~)
• ~g[2] = f[0] + f[2] = 1 + 3 = 4~ (submask của ~10_2~ là ~00_2, 10_2~)
• ~g[3] = f[0]+f[1]+f[2]+f[3] = 1+2+3+4 = 10~ (submask của ~11_2~ là tất cả)

Giới hạn

Chú ý: Brute force ~O(3^M)~ không đủ nhanh với ~M = 20~. Cần giải thuật ~O(M \cdot 2^M)~.