Vendelín has a part-time job in an "all for 1 euro" bargain store. He was given the task of putting several items into a row on one long shelf in the display window.
Vendelín is shape-blind: he only cares about the items' colours. This time, he sees that each of his items comes in one of just 4 colours: turquoise, magenta, beige and lavender (but don't worry, we've numbered them 0 through 3 for your convenience). Also, in order to attract customers, he wants each two adjacent items on the shelf to have different colours.
You're given an int n with 4 elements. For each i, Vendelín has n[i] items of colour i.
Compute and return the number of sequences of items such that no two adjacent items share the same colour. Since this number can get very large, return it modulo 1,000,000,009.
|Method signature:||int countSequences(int n)|
|(be sure your method is public)|
|-||n will contain exactly 4 elements.|
|-||Each element of n will be between 0 and 50,000, inclusive.|
|-||There will be at least 1 item, so the elements of n won't all be equal to 0.|
|-||At least 2 elements of n won't exceed 200.|
|There are 10 possible sequences of 1 turquoise (colour 0), 2 beige (colour 2) and 3 lavender (colour 3) items with no two adjacent items sharing the same colour. For example, (0,3,2,3,2,3) or (3,2,0,3,2,3) are valid sequences of colours. However, (3,2,2,3,2,3) isn't valid.|
|All 4! permutations of these items are valid.|
|There are way too many items of colour 3. In any sequence, there would be two adjacent items of this colour.|
|Make sure you're using 109+9 as the modulus!|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.