Равные множества сумм
Равные множества сумм
Рассмотрим множество натуральных чисел, меньших или равных n. Отметим, что все элементы множества различны. Порядок элементов в множестве не существенен, то есть {3, 5, 9} и {5, 9, 3} являются одинаковыми множествами.
Количество элементов во множестве и их сумму будем обозначать через k и s соответственно. Количество множеств, удовлетворяющих этому условию, конечно. Если n = 9, k = 3 и s = 23, то множество {6, 8, 9} будет единственным. Однако в общем случае множеств может быть и несколько. Если n = 9, k = 3 и s = 22, то оба из множеств {5, 8, 9} и {6, 7, 9} возможны.
Напишите программу, которая найдет количество множеств с заданными условиями.
Входные данные
Состоит из нескольких тестов, число которых не превышает 100.
Каждый тест состоит из одной строки, содержащей три целых числа n, k и s (1 ≤ n ≤ 20, 1 ≤ k ≤ 10 и 1 ≤ s ≤ 155).
Последняя строка содержит три нуля.
Выходные данные
Для каждого теста вывести одно число - количество множеств с заданными условиями. Никаких лишних символов выводить не следует.
Считайте, что количество искомых множеств не превышает 231
- 1.
9 3 23 9 3 22 10 3 28 16 10 107 20 8 102 20 10 105 20 10 155 3 4 3 4 2 11 0 0 0
1 2 0 20 1542 5448 1 0 0