m 50,
1 k 50). Then k lines follow each containing an integer ni
with
1 ni 50. The last test case is followed by a line containing two zeros.
| Sewing Buttons with Grandma |
After so many years of studying math in the Academy of Colombian Mathematics (ACM) in the tropic, Eloi has finally decided to visit his grandmother for the winter in the north hemisphere. ``Buttons and patches and the cold wind blowing, the days pass quickly when I am sewing'' she says - Eloi now remembers how grandma quilts have love in every stitch. As a matter of fact, he has decided to learn the useful handicraft art of sewing buttons with grandma.
Eloi has realized that there is an interesting mathematical puzzle related to the task of sewing buttons to the front of
a shirt. Given a collection of n1 buttons of color c1, n2 buttons of color c2, ..., nk buttons of color ck, and
a shirt with m front buttonholes, in how many ways the buttonholes can be assigned m buttons from the
n1 + ... + nk buttons?
The input consists of several test cases. The first line of each test case contains two integers m and k separated
by a blank (
1 m 50,
1 k 50). Then k lines follow each containing an integer ni
with
1 ni 50. The last test case is followed by a line containing two zeros.
The output consists of one line per test case containing the number of ways the m buttonholes can be assigned m buttons from the n1 + ... + nk buttons, assuming that the colors c1,..., ck are pairwise distinct.
1 3 3 1 1 3 2 4 2 3 2 1 1 0 0
3 7 0