整数拆分
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述：
一个整数总可以拆分为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
