eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сумма различными числами

Сумма различными числами

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Целое положительное число 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
Автор Dr. Jittat Fakcharoenphol
Источник 2013 ACM-ICPC Thailand Southern Programming Contest, Август 10, Задача H