### 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)

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

 `3` `1` `1` `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)

 `4` `1` `1` `1`
`Returns: 5029440`
 This time, the exact number of characters of each type is undefined.
3)

 `10` `1` `3` `3`
`Returns: 818019214`
4)

 `5` `2` `2` `2`
`Returns: 0`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10934

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14281&pm=10934

gojira_tc

#### Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

#### Problem categories:

Dynamic Programming, Math