Statistics

Problem Statement for "LittleElephantAndPermutationDiv1"

Problem Statement

This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

Little Elephant from the Zoo of Lviv likes permutations. A permutation of size N is a sequence (a1, ..., aN) that contains each of the numbers from 1 to N exactly once. For example, (3,1,4,5,2) is a permutation of size 5.

Given two permutations A = (a1, ..., aN) and B = (b1, ..., bN), the value magic(A,B) is defined as follows: magic(A,B) = max(a1,b1) + max(a2,b2) + ... + max(aN,bN).

You are given the int N. You are also given another int K. Let X be the number of pairs (A,B) such that both A and B are permutations of size N, and magic(A,B) is greater than or equal to K. (Note that A and B are not required to be distinct.) Return the value (X modulo 1,000,000,007).

Definition

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

Constraints

  • N will be between 1 and 50, inclusive.
  • K will be between 1 and 2500, inclusive.

Examples

  1. 1

    1

    Returns: 1

    For N=1 the only pair of permutations is ( (1), (1) ). The magic of this pair of permutations is 1, so we count it.

  2. 2

    1

    Returns: 4

    Now there are four possible pairs of permutations. They are shown below, along with their magic value. magic( (1,2), (1,2) ) = 1+2 = 3 magic( (1,2), (2,1) ) = 2+2 = 4 magic( (2,1), (1,2) ) = 2+2 = 4 magic( (2,1), (2,1) ) = 2+1 = 3 In all four cases the magic value is greater than or equal to K.

  3. 3

    8

    Returns: 18

  4. 10

    74

    Returns: 484682624

  5. 50

    1000

    Returns: 539792695

  6. 50

    1500

    Returns: 388279416

  7. 50

    1747

    Returns: 796754688

  8. 50

    1890

    Returns: 74859631

  9. 50

    1901

    Returns: 0

  10. 50

    2500

    Returns: 0

  11. 49

    1

    Returns: 846215923

  12. 50

    1

    Returns: 539792695

  13. 50

    12

    Returns: 539792695

  14. 50

    47

    Returns: 539792695

  15. 50

    477

    Returns: 539792695

  16. 47

    74

    Returns: 727118163

  17. 49

    1024

    Returns: 846215923

  18. 37

    857

    Returns: 217821562

  19. 1

    2500

    Returns: 0

  20. 17

    147

    Returns: 549544085

  21. 27

    13

    Returns: 769736937

  22. 39

    25

    Returns: 563428636

  23. 25

    470

    Returns: 791823464

  24. 43

    1342

    Returns: 642169192

  25. 9

    10

    Returns: 681893483

  26. 10

    2

    Returns: 189347824

  27. 37

    1

    Returns: 724179390

  28. 28

    128

    Returns: 473754387

  29. 50

    1490

    Returns: 225910723

  30. 50

    479

    Returns: 539792695

  31. 50

    799

    Returns: 539792695

  32. 50

    100

    Returns: 539792695

  33. 50

    200

    Returns: 539792695

  34. 50

    300

    Returns: 539792695

  35. 50

    1400

    Returns: 60959369

  36. 50

    1475

    Returns: 845285873

  37. 50

    1507

    Returns: 802018893

  38. 50

    1508

    Returns: 776302544

  39. 50

    1800

    Returns: 90855691

  40. 50

    1774

    Returns: 352388461

  41. 50

    1821

    Returns: 828487545

  42. 49

    1379

    Returns: 512339745

  43. 49

    100

    Returns: 846215923

  44. 49

    1500

    Returns: 49986203

  45. 30

    500

    Returns: 189153374

  46. 30

    507

    Returns: 841737670

  47. 30

    605

    Returns: 959770133

  48. 30

    777

    Returns: 0

  49. 15

    1

    Returns: 738721209

  50. 15

    125

    Returns: 449554103

  51. 50

    1600

    Returns: 468658077

  52. 49

    1717

    Returns: 951185172

  53. 50

    1300

    Returns: 801686140

  54. 50

    1700

    Returns: 38571275

  55. 50

    1340

    Returns: 853505117

  56. 49

    1234

    Returns: 243672630

  57. 50

    1444

    Returns: 224342980

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: