Задачі
Сума різними числами
Сума різними числами
Ціле додатнє число \textbf{n }можна записати у вигляді суми різних натуральних чисел декількома способами. Наприклад,
для \textbf{n }= \textbf{5 }існує \textbf{3 }способи: \textbf{5}, \textbf{2+3}, \textbf{1+4}.
для \textbf{n }= \textbf{6 }існує \textbf{4 }способи: \textbf{6}, \textbf{1+5}, \textbf{1+2+3}, \textbf{2+4}.
У цій задачі перестановка одних і тих же чисел вважається одним способом, тобто \textbf{1+2+3} теж саме, що \textbf{2+1+3} або \textbf{3+1+2} і т.д.
\InputFile
У першому рядку задано кількість тестів t (\textbf{1 }≤ \textbf{t }≤ \textbf{20}). Наступні \textbf{t }рядків містять самі тестові випадки у вигляді єдиного числа \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{2000}).
\OutputFile
Для кожного заданого числа n виведіть у окремому рядку кількість різних способів подання заданого числа у вигляді суми натуральних чисел, як це описано вище. Так як шукане число може бути достатньо великим, відповідь виведіть за модулем \textbf{100999}.
Вхідні дані #1
4 5 6 10 200
Вихідні дані #1
3 4 10 50568