Statistics

Problem Statement for "SequencePermutation"

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

  1. 3

    1

    Returns: 2

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

  2. 3

    0

    Returns: 1

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

  3. 3

    3

    Returns: 3

  4. 33

    1803

    Returns: 620284697

    Watch out for integer overflow!

  5. 2000

    2000

    Returns: 624672242

  6. 2000

    1999

    Returns: 736442792

  7. 1359

    493

    Returns: 983021627

  8. 1060

    1927

    Returns: 584847094

  9. 42

    430

    Returns: 342421067

  10. 1807

    1803

    Returns: 55323580

  11. 960

    43

    Returns: 420276508

  12. 1385

    325

    Returns: 459824111

  13. 1803

    1874

    Returns: 318524952

  14. 360

    328

    Returns: 81830564

  15. 330

    1896

    Returns: 753409667

  16. 1046

    1751

    Returns: 424847468

  17. 1805

    652

    Returns: 345904607

  18. 1661

    13

    Returns: 958945511

  19. 1103

    379

    Returns: 431103492

  20. 159

    757

    Returns: 391130813

  21. 900

    620

    Returns: 117542688

  22. 716

    676

    Returns: 143501420

  23. 231

    966

    Returns: 826739160

  24. 1040

    830

    Returns: 714238476

  25. 519

    150

    Returns: 484884543

  26. 91

    1556

    Returns: 680962793

  27. 579

    1501

    Returns: 159401917

  28. 1459

    492

    Returns: 528061050

  29. 1882

    1229

    Returns: 819686086

  30. 1360

    1238

    Returns: 974141345

  31. 711

    1530

    Returns: 554355658

  32. 397

    841

    Returns: 600079463

  33. 313

    997

    Returns: 247432456

  34. 1307

    726

    Returns: 646161865

  35. 1445

    83

    Returns: 479813196

  36. 537

    612

    Returns: 900541535

  37. 4

    0

    Returns: 1

  38. 4

    1

    Returns: 3

  39. 4

    8

    Returns: 12

  40. 4

    37

    Returns: 12

  41. 4

    180

    Returns: 12

  42. 4

    603

    Returns: 12

  43. 4

    1955

    Returns: 12

  44. 4

    2000

    Returns: 12

  45. 9

    0

    Returns: 1

  46. 9

    1

    Returns: 8

  47. 9

    8

    Returns: 5157

  48. 9

    37

    Returns: 181440

  49. 9

    180

    Returns: 181440

  50. 9

    603

    Returns: 181440

  51. 9

    1955

    Returns: 181440

  52. 9

    2000

    Returns: 181440

  53. 37

    0

    Returns: 1

  54. 37

    1

    Returns: 36

  55. 37

    8

    Returns: 144259152

  56. 37

    37

    Returns: 449431890

  57. 37

    180

    Returns: 604205239

  58. 37

    603

    Returns: 553768892

  59. 37

    1955

    Returns: 858671960

  60. 37

    2000

    Returns: 858671960

  61. 154

    0

    Returns: 1

  62. 154

    1

    Returns: 153

  63. 154

    8

    Returns: 291852744

  64. 154

    37

    Returns: 92655949

  65. 154

    180

    Returns: 625619368

  66. 154

    603

    Returns: 988766192

  67. 154

    1955

    Returns: 718817285

  68. 154

    2000

    Returns: 52122500

  69. 701

    0

    Returns: 1

  70. 701

    1

    Returns: 700

  71. 701

    8

    Returns: 133969418

  72. 701

    37

    Returns: 215816380

  73. 701

    180

    Returns: 879039217

  74. 701

    603

    Returns: 399330037

  75. 701

    1955

    Returns: 764217826

  76. 701

    2000

    Returns: 994100762

  77. 1902

    0

    Returns: 1

  78. 1902

    1

    Returns: 1901

  79. 1902

    8

    Returns: 162757453

  80. 1902

    37

    Returns: 870047029

  81. 1902

    180

    Returns: 578532001

  82. 1902

    603

    Returns: 918783553

  83. 1902

    1955

    Returns: 796444949

  84. 1902

    2000

    Returns: 14589797

  85. 2000

    0

    Returns: 1

  86. 2000

    1

    Returns: 1999

  87. 2000

    8

    Returns: 285254861

  88. 2000

    37

    Returns: 835883399

  89. 2000

    180

    Returns: 779254402

  90. 2000

    603

    Returns: 342371180

  91. 2000

    1955

    Returns: 93454284

  92. 2000

    2000

    Returns: 624672242

  93. 5

    0

    Returns: 1

  94. 5

    1

    Returns: 4

  95. 5

    9

    Returns: 60

  96. 5

    10

    Returns: 60

  97. 5

    4

    Returns: 30

  98. 5

    5

    Returns: 41

  99. 7

    0

    Returns: 1

  100. 7

    1

    Returns: 6

  101. 7

    20

    Returns: 2520

  102. 7

    21

    Returns: 2520

  103. 7

    10

    Returns: 1406

  104. 7

    11

    Returns: 1687

  105. 10

    0

    Returns: 1

  106. 10

    1

    Returns: 9

  107. 10

    44

    Returns: 1814400

  108. 10

    45

    Returns: 1814400

  109. 10

    22

    Returns: 970337

  110. 10

    23

    Returns: 1094812

  111. 20

    0

    Returns: 1

  112. 20

    1

    Returns: 19

  113. 20

    189

    Returns: 140261063

  114. 20

    190

    Returns: 140261063

  115. 20

    94

    Returns: 570130536

  116. 20

    95

    Returns: 848084299

  117. 40

    0

    Returns: 1

  118. 40

    1

    Returns: 39

  119. 40

    779

    Returns: 73330682

  120. 40

    780

    Returns: 73330682

  121. 40

    389

    Returns: 36665341

  122. 40

    390

    Returns: 458379451

  123. 50

    0

    Returns: 1

  124. 50

    1

    Returns: 49

  125. 50

    1224

    Returns: 874846958

  126. 50

    1225

    Returns: 874846958

  127. 50

    612

    Returns: 627233708

  128. 50

    613

    Returns: 133753696

  129. 55

    0

    Returns: 1

  130. 55

    1

    Returns: 54

  131. 55

    1484

    Returns: 128230434

  132. 55

    1485

    Returns: 128230434

  133. 55

    742

    Returns: 659991788

  134. 55

    743

    Returns: 561680918

  135. 60

    0

    Returns: 1

  136. 60

    1

    Returns: 59

  137. 60

    1769

    Returns: 730386355

  138. 60

    1770

    Returns: 730386355

  139. 60

    884

    Returns: 865193182

  140. 60

    885

    Returns: 69286002

  141. 61

    0

    Returns: 1

  142. 61

    1

    Returns: 60

  143. 61

    1829

    Returns: 553567259

  144. 61

    1830

    Returns: 553567259

  145. 61

    914

    Returns: 776783634

  146. 61

    915

    Returns: 778468928

  147. 62

    0

    Returns: 1

  148. 62

    1

    Returns: 61

  149. 62

    1890

    Returns: 321169752

  150. 62

    1891

    Returns: 321169752

  151. 62

    945

    Returns: 512633378

  152. 62

    946

    Returns: 607582062

  153. 63

    0

    Returns: 1

  154. 63

    1

    Returns: 62

  155. 63

    1952

    Returns: 233694196

  156. 63

    1953

    Returns: 233694196

  157. 63

    976

    Returns: 781725991

  158. 63

    977

    Returns: 981645272

  159. 64

    0

    Returns: 1

  160. 64

    1

    Returns: 63

  161. 64

    1999

    Returns: 328984443

  162. 64

    2000

    Returns: 331097931

  163. 64

    999

    Returns: 767887354

  164. 64

    1000

    Returns: 97529581

  165. 65

    0

    Returns: 1

  166. 65

    1

    Returns: 64

  167. 65

    1999

    Returns: 594180458

  168. 65

    2000

    Returns: 272590452

  169. 65

    999

    Returns: 106840998

  170. 65

    1000

    Returns: 83957813

  171. 63

    1951

    Returns: 233694195

  172. 63

    1950

    Returns: 233694134

  173. 2

    0

    Returns: 1

  174. 2

    1

    Returns: 1

  175. 2

    2

    Returns: 1

  176. 2

    3

    Returns: 1

  177. 2

    2000

    Returns: 1

  178. 2

    1999

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: