You are given an array A of n integers. Let the maximum possible bitwise OR of any subsequence of elements of the array be M. You need to print n integers numbered from 1 to n. The i^th integer denotes the number of distinct subsequences of size i of the array whose bitwise OR is equal to M. Since the integers can be very large, print each of them modulo 10⁹+ 7.

Note: Two subsequences are distinct if there exists at least one postion of the array which is included in one of the subsequences and not so in the other.

INPUT FORMAT

The first line contains a single integer n.
The second line contains n space separated integers denoting the array A.

CONSTRAINTS

1 ≤ n ≤ 5000

0 ≤ A_i < 2¹²

OUTPUT FORMAT

Print a single line containing n space separated integers as specified.