eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 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 и т.д.

Giriş verilənləri

В первой строке задано количество тестов t (1 t 20). Следующие t строк содержат сами тесты в виде единственного числа n (1 n 2000).

Çıxış verilənləri

Для каждого заданного числа n выведите в отдельной строке количество различных способов представления заданного числа в виде суммы натуральных чисел, как описано выше. Так как искомое число может быть достаточно большим, ответ выведите по модулю 100999.

Nümunə

Giriş verilənləri #1
4
5
6
10
200
Çıxış verilənləri #1
3
4
10
50568
Müəllif Dr. Jittat Fakcharoenphol
Mənbə 2013 ACM-ICPC Thailand Southern Programming Contest, Август 10, Задача H