| ||A password is a sequence of alphanumeric characters. Count the number of different passwords of length N which contain at least L lowercase characters, at least U uppercase characters and at least D digits. Return this number modulo 1,000,000,009.|
|Parameters:||int, int, int, int|
|Method signature:||int countValid(int N, int L, int U, int D)|
|(be sure your method is public)|
|-||N will be between 1 and 200,000, inclusive.|
|-||L will be between 0 and N, inclusive.|
|-||U will be between 0 and N, inclusive.|
|-||D will be between 0 and N, inclusive.|
|The only valid passwords are those consisting of digits only. There are 100 2-digit sequences.
|A valid password will contain exactly one lowercase and one uppercase letter and one digit. Since they can come in any order, there are 3!*26*26*10 = 40560 possible combinations.
|This time, the exact number of characters of each type is undefined.