Problem Statement 
 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. 

Definition 
 Class:  Passwords  Method:  countValid  Parameters:  int, int, int, int  Returns:  int  Method signature:  int countValid(int N, int L, int U, int D)  (be sure your method is public) 




Constraints 
  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. 

Examples 
0)  
  Returns: 100  The only valid passwords are those consisting of digits only. There are 100 2digit sequences.



1)  
  Returns: 40560  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.



2)  
  Returns: 5029440  This time, the exact number of characters of each type is undefined.



3)  
 
4)  
 