题目描述

给定 n 和 X0,X1,...,Xn-1,求解 Y0,Y1,...,Yn-1,其中:

$$Y_i = \sum_{j=0}^{n-1}X_j\times f(i\oplus j)$$

f(x) 等于把 x 写成二进制后 1 的个数,比如说:

f(0)=0 , f(1)=1 , f(4)=1 , f(7)=3

其中 $\oplus$ 表示二进制下的按位异或运算。

请依次输出 Y0,Y1,...,Yn-1 对 $10^9+7$ 取模的结果。

输入格式

输入第一行为一个正整数 n

输入第二行为 n 个非负整数,第 i 个数表示 Xi-1

输出格式

输出仅一行 n 个非负整数,第 i 个数表示 Yi-1 对 $10^9+7$ 取模的结果。

样例输入

3

1 1 1

样例输出

2 3 3

数据范围及约定

测试数据点 n Xi 特殊性质
1 <= 10 <= 10
2 <= 100 <= 100
3 <= 1000 <= 1000
4 = 65536 <= 109 所有 A都相同
5 <= 105 <= 109 所有 A都相同
6,7,8,9,10 <= 105 <= 109