### Problem Statement

You are given a sequence 1, 2, .., N. M times, you pick two adjacently located numbers in the sequence and swap them. Return the number of different final sequences that can be obtained modulo 1,000,000,009.

### Definition

 Class: SequencePermutation Method: determineConfigurations Parameters: int, int Returns: int Method signature: int determineConfigurations(int N, int M) (be sure your method is public)

### Constraints

-N will be between 2 and 2000, inclusive.
-M will be between 0 and 2000, inclusive.

### Examples

0)

 `3` `1`
`Returns: 2`
 The possible resulting sequences are (1,3,2) and (2,1,3).
1)

 `3` `0`
`Returns: 1`
 The only possible resulting sequence without swapping any of the elements is the original sequence, that is, (1,2,3).
2)

 `3` `3`
`Returns: 3`
3)

 `33` `1803`
`Returns: 620284697`
 Watch out for integer overflow!

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14286&pm=10815

dolphinigle

#### Testers:

SnapDragon , Rustyoldman , marek.cygan , timmac , ivan_metelsky , Egor

#### Problem categories:

Dynamic Programming