SEQUENCE PERMUTATION

I have not any algorithm for this problem. Can I solve this problem with DP?
Any algorithm please.

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.
Constraints
-N will be between 2 and 2000, inclusive.
-M will be between 0 and 2000, inclusive.