Under construction

Still being built. Things may change

Equal Sum Sets

Interview

Time limit3sMemory limit128 MB

Summary
Count subsets of {1..n} with exactly k elements that sum to s for each dataset.
Level

Easy3 of 10

Topics
Dynamic programming, Combinatorics
Solved
No attempts yet

Problem

Consider sets of positive integers that are at most nn. All elements of a set are different, and the order of elements does not matter, so {3, 5, 9} and {5, 9, 3} are the same set.

Once the number of elements is fixed to kk and their sum to ss, few sets satisfy both conditions. For n=9n = 9, k=3k = 3 and s=23s = 23, the set {6, 8, 9} is the only one. In general there can be more than one. For n=9n = 9, k=3k = 3 and s=22s = 22, both {5, 8, 9} and {6, 7, 9} satisfy the conditions.

Write a program that counts the sets satisfying the given conditions.

Input

The input consists of several datasets. The number of datasets does not exceed 100.

Each dataset is one line holding the integers nn, kk and ss, separated by a space. Assume 1≤n≤201 \le n \le 20, 1≤k≤101 \le k \le 10 and 1≤s≤1551 \le s \le 155.

A line with three zeros marks the end of the input.

Output

For each dataset, print the number of sets satisfying the conditions on one line. Print no other characters.

The number of sets does not exceed 231−12^{31} - 1.

Examples1

  1. Example 1

    Input
    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
    
    Expected output
    1
    2
    0
    20
    1542
    5448
    1
    0
    0