题目描述：

一个整数总可以拆分为2的幂的和，例如：7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。求若干个数的拆分方式，种类可能会 很多，结果对10^9取模。

输入格式：

第一行输入一个数n，表示有n个数。 第二行n个数，表示每个要拆分的数ai。

输出格式：

输出n行，每一行一个数表示有多少种拆分方式。

样例：

2
7 4

6
4

提示

1<= ai，n <= 10^7