Statistics

Problem Statement for "CarelessSecretary"

Problem Statement

The king needs to distribute instructions to all his ministers. Since each minister requires a unique set of instructions, he writes a personalized letter for each minister and hands them off to his secretary to deliver.

Unfortunately, the king's secretary is a really careless fellow. He forgets that each minister has his own personalized letter, and he delivers a random letter to each minister instead. After he realizes his mistake, he begins to call the ministers one by one and asks them if they got the correct letter. So far, he has called K of the N ministers, and to his horror, none of the K ministers has received the correct letter.

The king is furious with his secretary, but he decides to give him one last chance to save his job. He asks the secretary the following question. In how many ways was it possible for him to distribute the letters so that the current situation would arise? In other words, how many different ways could the letters have been distributed such that a wrong letter went to each of the K ministers that has been called so far? Two ways are considered different if at least one minister gets a different letter. If the secretary can answer this question correctly, he can keep his job. Your job is to help the secretary by calculating the correct answer for him. Since the answer can be very large, return the answer modulo 1,000,000,007.

Definition

Class:
CarelessSecretary
Method:
howMany
Parameters:
int, int
Returns:
int
Method signature:
int howMany(int N, int K)
(be sure your method is public)

Constraints

  • N will be between 1 and 1000, inclusive.
  • K will be between 1 and N, inclusive.
  • K will be between 1 and 12, inclusive.

Examples

  1. 2

    1

    Returns: 1

    There are two ministers, and one of them must not get his own letter. Therefore, the only possibility is that they get each other's letters.

  2. 3

    1

    Returns: 4

    The minister who must not get his own letter might get any of the two remaining letters. For each possibility, there are 2 ways to give the letters to the other ministers. Hence, the answer is 2*2 = 4.

  3. 9

    9

    Returns: 133496

  4. 5

    1

    Returns: 96

  5. 6

    2

    Returns: 504

  6. 3

    3

    Returns: 2

    Three ministers, and none of them get their own letters.

  7. 7

    4

    Returns: 2790

  8. 9

    1

    Returns: 322560

  9. 4

    2

    Returns: 14

  10. 3

    2

    Returns: 3

  11. 35

    7

    Returns: 165264376

  12. 12

    7

    Returns: 264398280

  13. 39

    2

    Returns: 853640439

  14. 82

    8

    Returns: 816228267

  15. 8

    1

    Returns: 35280

  16. 28

    8

    Returns: 325247893

  17. 28

    10

    Returns: 545742228

  18. 34

    6

    Returns: 549243636

  19. 22

    8

    Returns: 233312314

  20. 80

    5

    Returns: 885821017

  21. 57

    9

    Returns: 499972457

  22. 38

    2

    Returns: 286941793

  23. 44

    9

    Returns: 48254687

  24. 15

    9

    Returns: 607719663

  25. 52

    2

    Returns: 769124764

  26. 46

    9

    Returns: 802141913

  27. 3

    2

    Returns: 3

  28. 12

    9

    Returns: 224406930

  29. 36

    4

    Returns: 382568184

  30. 4

    3

    Returns: 11

  31. 16

    5

    Returns: 285736828

  32. 20

    4

    Returns: 969845951

  33. 56

    1

    Returns: 805995337

  34. 30

    3

    Returns: 711564780

  35. 88

    2

    Returns: 813089172

  36. 100

    9

    Returns: 26120004

  37. 4

    1

    Returns: 18

  38. 9

    9

    Returns: 133496

  39. 15

    2

    Returns: 544798427

  40. 50

    2

    Returns: 492932547

  41. 454

    6

    Returns: 264783526

  42. 435

    5

    Returns: 707553019

  43. 1

    1

    Returns: 0

  44. 551

    2

    Returns: 14453556

  45. 956

    5

    Returns: 859696510

  46. 554

    3

    Returns: 253845022

  47. 744

    3

    Returns: 206947598

  48. 552

    8

    Returns: 56551377

  49. 409

    5

    Returns: 537704585

  50. 127

    4

    Returns: 618115958

  51. 584

    8

    Returns: 321140008

  52. 335

    10

    Returns: 521902250

  53. 438

    9

    Returns: 837019405

  54. 300

    3

    Returns: 327737405

  55. 620

    9

    Returns: 578650164

  56. 198

    4

    Returns: 516897588

  57. 234

    9

    Returns: 74500773

  58. 48

    4

    Returns: 809901475

  59. 161

    5

    Returns: 600697191

  60. 129

    10

    Returns: 866029002

  61. 532

    6

    Returns: 316241268

  62. 208

    10

    Returns: 869800440

  63. 996

    10

    Returns: 160364229

  64. 369

    4

    Returns: 262374292

  65. 919

    3

    Returns: 79877109

  66. 674

    10

    Returns: 90244251

  67. 632

    9

    Returns: 980800698

  68. 701

    3

    Returns: 513106734

  69. 913

    4

    Returns: 39212854

  70. 808

    3

    Returns: 120406126

  71. 714

    9

    Returns: 466134693

  72. 290

    4

    Returns: 952802197

  73. 231

    1

    Returns: 402927102

  74. 742

    1

    Returns: 316005800

  75. 279

    1

    Returns: 994114427

  76. 613

    4

    Returns: 473211301

  77. 598

    1

    Returns: 958575611

  78. 546

    3

    Returns: 520095478

  79. 730

    5

    Returns: 81533245

  80. 390

    8

    Returns: 121386928

  81. 937

    4

    Returns: 197578635

  82. 528

    4

    Returns: 917417043

  83. 292

    10

    Returns: 603021680

  84. 174

    3

    Returns: 550385207

  85. 631

    5

    Returns: 750126965

  86. 564

    1

    Returns: 144546026

  87. 947

    4

    Returns: 599997623

  88. 918

    8

    Returns: 702131681

  89. 147

    9

    Returns: 767319001

  90. 456

    2

    Returns: 867928804

  91. 1

    1

    Returns: 0

  92. 10

    10

    Returns: 1334961

  93. 1000

    10

    Returns: 487930807

  94. 1000

    9

    Returns: 325212876

  95. 1000

    8

    Returns: 389510806

  96. 2

    2

    Returns: 1

  97. 271

    11

    Returns: 575654024

  98. 138

    11

    Returns: 878192827

  99. 918

    12

    Returns: 265160497

  100. 471

    12

    Returns: 618229700

  101. 110

    12

    Returns: 105989846

  102. 28

    11

    Returns: 301237487

  103. 861

    11

    Returns: 377628194

  104. 147

    12

    Returns: 311361157

  105. 613

    11

    Returns: 210780205

  106. 443

    11

    Returns: 8952148

  107. 938

    11

    Returns: 189358954

  108. 699

    12

    Returns: 611843088

  109. 330

    12

    Returns: 57063700

  110. 682

    11

    Returns: 730990318

  111. 994

    11

    Returns: 825241079

  112. 418

    12

    Returns: 147766199

  113. 51

    11

    Returns: 708277193

  114. 417

    11

    Returns: 633487548

  115. 367

    12

    Returns: 152623713

  116. 587

    11

    Returns: 316002078

  117. 1000

    12

    Returns: 981713415

  118. 999

    12

    Returns: 244490877

  119. 265

    7

    Returns: 334136939

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: