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