OOPS! They did it Again |
The Aliens of the Planet Muzambaro have re-elected their universally unpopular leader. After the result was announced the disappointed newspapers of some other planets had the headline ``OOPS! They did it again." Well now it is party time in Muzambaro and so they are planning to decorate k Skyscrapers of their city with lights.
The longest street of planet Muzambaro is ``The Deaf Street". The properties of this street are stated below:
From these (high - low + 1) buildings they want to select k buildings to decorate with lights in the following way:
Now given the value of low, high and k the Aliens of Planet Muzambaro wants to determine in how many ways they can choose the k buildings. They have written a brute force program to find out the answer but they know that it wont terminate even in four years!! That is why they are now asking for your help. Can you help them?
The input file contains less than 1001 lines of inputs. The description of each line of input is given below:
Each line of input describes one particular scenario. There are three
integers low, high (
0 < low < high < 20000001)
and k (
1 < k(high - low + 1)) in each line. The meaning of low,
high and k are given in the problem statement above.
Input is terminated by a case where low = high = k = 0 which should not be processed.
For each line of input you should produce one line of output. This line should contain the serial of output followed by an integer, which indicates the number of ways they can choose the k buildings. Look at the output for sample input for details.
1 10 4 2 10 4 1 48 2 1222 2329228 2 0 0 0
Case 1: 4 Case 2: 3 Case 3: 552 Case 4: 1354902984009