概率
题号：NC282099
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

现在有一个长度为 n 的序列 a_1,a_2,\cdots,a_n，序列中的每个元素互不相同。对于非负整数 k，定义 p_k 代表从序列中随机选两个不同的整数 x 和 y 后，这两个整数满足条件 x \oplus y\ge 2^k 的概率，这里， x \oplus y 表示 x 和 y 做二进制异或运算 (XOR) 的结果。

对于小于等于 30 的每个非负整数 k，请求出 p_k 模 10^9+7 的值。具体请看输出格式要求。

输入描述:

输入第一行有一个整数 n(2\le n\le 10^5)，表示序列长度。

输入第二行有 n 个整数 a_1,a_2,\cdots,a_n(0\le a_i\le 10^9)，代表这个序列的每个元素。

输出描述:

输出一行 31 个由单个空格分隔的整数，对于第 k 个整数，输出 p_{k-1} 模 10^9+7 的值。

可以证明对于每个非负整数 k，p_k 能够表示为有理数 \frac p q，其中 p 和 q 是正整数且 q \not\equiv 0\pmod M。为了避免精度问题，请输出整数 (p\cdot q^{-1}\pmod M) 作为答案，其中 M=10^9+7，q^{-1} 是满足 qq^{-1}\equiv 1\pmod M 的整数。
示例1

输入

复制 
3
1 3 5

输出

复制 
1 1 666666672 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0