子集和问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一个正整数可以通过多种方式写成唯一的正整数的和,比如:

N=5,有3种方式:52+31+4

N=6,有4种方式:61+51+2+32+4

注意相同加数不同排列计算为一个,比如1+2+32+1+33+1+2等算作一个子集和。

Input

 第一行是一个整数n表示测试样例的个数(1n20),接下来的n行每行一个整数N,(1N2000).

Output

 每一个测试整数的子集和表示方式的数目,为了便于表达输出的值mod100999.

Sample Input

4
5
6
10
200

Sample Output

3 
4 
10 
50568

Hint

 

Source

中国海洋大学第四届朗讯杯初级组