600202 - 数根STEP2
有n个人，每个人手上有一个数字a_i，若k个人的数字之和的数根为d，则可以打开d号宝箱。求打开1-9号宝箱的方案有多少种？
Input
第一行，一个整数n。
接下来n行，每行一个整数a_i。
对于100%的数据：
1 \le n \le 10^5；
1 \le a_i \le 10^9。
Output
依次输出打开1-9号宝箱的方案数对10000007取模的结果。
Examples
Input
2 9 8
Output
0 0 0 0 0 0 0 2 1
Input
3 9 8 7
Output
0 0 0 0 0 2 2 2 1
Input
6 9 8 7 6 5 4
Output
6 6 8 8 6 8 6 8 7