Statistics

Problem Statement for "LISNumber"

Problem Statement

Let A be a sequence of integers. The LISNumber of A is the smallest positive integer L such that A can be obtained by concatenating L strictly increasing sequences. For example, the LISNumber of A = {1, 4, 4, 2, 6, 3} is 4, since we can obtain A as {1, 4} + {4} + {2, 6} + {3}, and there is no way to create A by concatenating 3 (or fewer) strictly increasing sequences. The LISNumber of a strictly increasing sequence is 1.


You have N types of cards. For each i, 0 <= i < N, you have cardsnum[i] cards of the i-th type. Each card of the i-th type contains the number i.


You are given the int[] cardsnum and an int K. You want to arrange all the cards you have into a row in such a way that the resulting sequence of integers has LISNumber K. Note that you must use all the cards you have, you can only choose their order.


Let X be the number of different valid sequences you can produce. Compute and return the number X, modulo 1,000,000,007.

Definition

Class:
LISNumber
Method:
count
Parameters:
int[], int
Returns:
int
Method signature:
int count(int[] cardsnum, int K)
(be sure your method is public)

Constraints

  • cardsnum will contain between 1 and 36 elements, inclusive.
  • Each element of cardsnum will be between 1 and 36, inclusive.
  • K will be between 1 and 1296, inclusive.

Examples

  1. {1, 1, 1}

    2

    Returns: 4

    In this case, there are 3 types of cards and you have one of each. Among the 6 sequences you can make, the following 4 have LISNumber 2: {0, 2, 1} {1, 0, 2} {1, 2, 0} {2, 0, 1}

  2. {2}

    1

    Returns: 0

    The only sequence you can make is {0, 0} and its LISNumber is 2.

  3. {36, 36, 36, 36, 36}

    36

    Returns: 1

    Only the sequence {0, 1, 2, 3, 4, 0, 1, 2, 3, 4, ... (36 times) ... } has LISNumber 36.

  4. {3, 2, 11, 5, 7}

    20

    Returns: 474640725

  5. {31, 4, 15, 9, 26, 5, 35, 8, 9, 7, 9, 32, 3, 8, 4, 6, 26}

    58

    Returns: 12133719

  6. {27, 18, 28, 18, 28, 4, 5, 9, 4, 5, 23, 5, 36, 28, 7, 4, 7, 13, 5, 26, 6, 24, 9, 7, 7, 5, 7, 24, 7, 9, 36, 9, 9, 9, 5, 9}

    116

    Returns: 516440918

  7. {1}

    1

    Returns: 1

  8. {1}

    2

    Returns: 0

  9. {36}

    35

    Returns: 0

  10. {36}

    36

    Returns: 1

  11. {36, 36}

    36

    Returns: 1

  12. {36, 36}

    50

    Returns: 844733697

  13. {36, 36}

    72

    Returns: 1

  14. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    1

    Returns: 1

  15. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    2

    Returns: 719476223

  16. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    35

    Returns: 719476223

  17. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    36

    Returns: 1

  18. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    35

    Returns: 0

  19. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    36

    Returns: 1

  20. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    37

    Returns: 325376233

  21. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    40

    Returns: 434819765

  22. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    100

    Returns: 913960027

  23. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    199

    Returns: 895595539

  24. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    301

    Returns: 75862305

  25. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    450

    Returns: 408337909

  26. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    603

    Returns: 837964853

  27. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    701

    Returns: 879369484

  28. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    890

    Returns: 760740831

  29. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    1020

    Returns: 919208475

  30. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    1111

    Returns: 455044173

  31. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    1294

    Returns: 738987967

  32. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    1295

    Returns: 325376233

  33. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}

    1296

    Returns: 1

  34. {1, 9, 9, 2, 5, 7, 3, 1, 19}

    53

    Returns: 423002411

  35. {2, 30, 9, 2, 2, 1, 4, 2, 5}

    29

    Returns: 0

  36. {9, 6, 4, 4, 9, 4, 2}

    37

    Returns: 262461

  37. {8, 1, 1, 15, 5, 9}

    8

    Returns: 0

  38. {6, 7, 8, 2}

    7

    Returns: 0

  39. {5, 1, 2, 8, 3, 35}

    52

    Returns: 110722005

  40. {23, 6, 35, 6, 9}

    11

    Returns: 0

  41. {5, 8, 14, 5, 8, 9}

    1

    Returns: 0

  42. {1, 4, 7, 8, 7, 8, 7}

    25

    Returns: 504608108

  43. {2, 8, 5, 9, 6, 5, 7, 4, 6}

    1

    Returns: 0

  44. {8, 9, 8, 8, 9, 8, 4, 3, 4, 1}

    36

    Returns: 954169340

  45. {8, 34, 9, 3, 8, 13, 7, 8}

    22

    Returns: 0

  46. {28, 34, 28, 29, 32, 33, 30, 34, 31, 26, 26, 31, 34, 25, 35, 25, 32, 26, 35, 26, 36, 31, 28, 36, 30, 34, 27, 29, 31, 25, 35, 30, 25, 32}

    1010

    Returns: 730067133

  47. {26, 36, 25, 30, 30, 36, 32, 29, 29, 27, 33, 30, 35, 32, 33, 29, 32, 27, 35, 28, 36, 35, 28, 33, 31, 35, 29, 30, 26, 34, 29, 25, 25, 35, 28, 36}

    1023

    Returns: 875688565

  48. {31, 26, 31, 35, 35, 35, 34, 31, 29, 31, 28, 28, 27, 34, 31, 29, 36, 33, 34, 26, 28, 35, 25, 32, 34, 33, 28, 33, 25, 28, 32, 36, 30, 27}

    995

    Returns: 517344082

  49. {35, 25, 26, 31, 36, 29, 28, 27, 30, 36, 27, 30, 32, 32, 29, 33, 35, 33, 35, 36, 25, 28, 34, 25, 32, 34, 27, 31, 36, 34, 35, 25, 29, 25, 33, 33}

    1089

    Returns: 730809050

  50. {26, 27, 36, 36, 35, 29, 26, 30, 35, 30, 28, 27, 31, 34, 27, 25, 33, 35, 28, 33, 36, 29, 31, 25, 33, 29, 30, 26, 30, 30, 36, 31, 34, 26, 32, 32}

    1002

    Returns: 153211567

  51. {30, 25, 34, 26, 26, 33, 31, 36, 29, 34, 33, 27, 27, 25, 25, 26, 34, 26, 25, 31, 32, 25, 31, 26, 33, 33, 27, 30, 32, 29, 30, 32}

    911

    Returns: 927585368

  52. {29, 28, 30, 32, 35, 35, 30, 27, 32, 26, 33, 29, 28, 29, 28, 34, 28, 30, 29, 33, 29, 36, 34, 26, 36, 25, 32, 30, 28, 28, 27, 35, 28}

    951

    Returns: 47891725

  53. {25, 36, 34, 28, 33, 33, 36, 29, 25, 32, 34, 32, 29, 36, 31, 25, 27, 32, 35, 36, 36, 29, 34, 30, 35, 31, 31, 26, 32, 32, 32, 25, 35, 29}

    979

    Returns: 896969667

  54. {34, 32, 32, 30, 32, 34, 33, 31, 36, 34, 36, 28, 35, 27, 27, 33, 34, 30, 33, 26, 33, 33, 32, 25, 36, 28, 27, 34, 32, 31, 29, 27, 34}

    1004

    Returns: 291266673

  55. {35, 36, 26, 31, 29, 33, 32, 30, 29, 32, 36, 33, 33, 29, 27, 36, 33, 33, 26, 30, 34, 30, 32, 25, 33, 31, 33, 31, 34, 36, 27, 33, 32, 29}

    1044

    Returns: 830962532

  56. {29, 31, 27, 31, 28, 26, 33, 32, 33, 32, 35, 32, 25, 25, 28, 31, 35, 36, 25, 33, 28, 35, 25, 29, 34, 30, 25, 33, 29, 31, 25, 28, 32, 26, 32, 32}

    1053

    Returns: 939635636

  57. {31, 28, 35, 35, 31, 26, 26, 26, 30, 27, 27, 27, 26, 29, 33, 27, 32, 31, 29, 29, 32, 29, 28, 34, 27, 26, 25, 26, 27, 29, 35, 31, 32, 31, 25}

    1011

    Returns: 677167627

  58. {28, 25, 23, 19, 1, 33, 17, 18, 29, 30, 8, 35, 36, 27, 20, 9, 3, 11, 31, 8, 10, 31, 17, 28, 4, 33, 11, 4, 29, 28, 19, 1, 19, 21, 16, 29}

    374

    Returns: 527963479

  59. {27, 3, 30, 23, 4, 10, 5, 17, 20, 24, 9, 18}

    133

    Returns: 374088099

  60. {13, 10, 11, 7, 6, 32, 30, 5, 6, 16, 36, 25, 18, 30, 20, 17, 32, 4, 22}

    4

    Returns: 0

  61. {10, 18, 22, 12, 31, 4, 11, 29, 27, 11, 23, 31, 11, 23, 5, 3, 15, 32, 10, 8, 14, 18, 14, 20, 7}

    209

    Returns: 584411839

  62. {15, 17, 29, 32, 13, 14, 30, 31, 11, 36, 1, 33, 25, 27, 7, 29, 22, 7, 29, 29, 6, 13, 12, 24, 27, 30, 13, 33, 5, 21}

    32

    Returns: 0

  63. {5, 34, 17, 23, 26, 22, 1, 23, 22, 10, 29, 4, 31, 8, 5, 23}

    273

    Returns: 456032695

  64. {20, 15, 36, 17, 20, 17, 2}

    95

    Returns: 842901551

  65. {18, 29, 22, 23, 11}

    92

    Returns: 264914462

  66. {8, 14, 11, 10, 17, 11, 4, 3, 22, 29, 9, 1, 7, 11, 32, 12, 12, 1}

    193

    Returns: 946863399

  67. {16, 32, 11, 1, 16, 29, 29, 6, 19}

    125

    Returns: 305146898

  68. {22, 27, 22, 22, 32, 22, 10, 29, 21, 19, 17, 29, 34, 14, 22, 20, 19, 35, 22, 16, 2, 8, 23, 23, 21, 10, 28, 10, 35}

    526

    Returns: 145381527

  69. {9, 29, 36, 8, 7, 26, 31}

    36

    Returns: 373708720

  70. {5, 35, 19, 16, 4, 5, 23, 36, 10, 3, 18, 28, 7, 21, 27, 32, 14, 11, 36, 3}

    149

    Returns: 883854400

  71. {22, 19, 21, 2, 7}

    39

    Returns: 740639180

  72. {10}

    8

    Returns: 0

  73. {3, 11, 23, 12, 7, 19, 3, 14, 29, 7}

    25

    Returns: 0

  74. {29, 7, 33, 21, 28, 21, 21, 26, 27, 29, 3, 17, 18, 36, 23, 23, 2, 10}

    340

    Returns: 690039

  75. {14, 12, 2, 9, 28, 33, 17, 13, 22, 18, 29, 10, 10}

    199

    Returns: 333645981

  76. {20, 20, 22, 33, 20, 11, 5, 23, 23, 3, 3, 6, 12, 2, 15, 23, 5, 6, 25, 22, 1, 9, 5, 26, 11}

    32

    Returns: 0

  77. {33, 6, 29, 12, 17, 12, 9, 31, 28, 21, 26, 28, 24, 11, 11, 2, 33, 27, 32, 14, 13, 1, 2, 4, 11, 17, 15, 35, 20, 12, 2, 31}

    345

    Returns: 11369158

  78. {29, 11, 8, 31, 10, 14, 10, 20, 20, 30, 7, 24, 6, 14, 9, 1, 19, 17, 29, 16, 30, 6, 23, 10, 32, 33, 1, 10, 19, 2, 1, 20}

    34

    Returns: 52653381

  79. {24, 31, 24, 6, 11, 1, 26, 32, 3, 11, 25, 15, 32, 24, 11, 27, 5, 29, 18, 14, 32, 23, 13, 5, 15, 10, 30, 19, 11, 23, 15}

    27

    Returns: 0

  80. {11, 8, 33, 9, 13, 22, 28, 29, 25, 4}

    31

    Returns: 0

  81. {21, 32, 30, 7, 11, 20, 2, 33, 20, 22, 20, 5}

    66

    Returns: 771570564

  82. {6, 29, 31}

    59

    Returns: 147629880

  83. {27, 18, 28, 18, 28, 4, 5, 9, 4, 5, 23, 5, 36, 28, 7, 4, 7, 13, 5, 26, 6, 24, 9, 7, 7, 5, 7, 24, 7, 9, 36, 9, 9, 9, 5, 9 }

    116

    Returns: 516440918

  84. {35, 23, 11, 28, 19, 8, 7, 30, 1, 35, 26, 2, 25, 7, 19, 14, 35, 36, 13, 18, 34, 8, 27, 34, 17, 24, 23, 35, 16, 18, 11, 33, 14, 28, 17, 13 }

    1288

    Returns: 0

  85. {30, 32, 31, 31, 34, 36, 30, 32, 32, 33, 30, 32, 32, 33, 35, 34, 32, 30, 34, 31, 35, 31, 35, 30, 35, 36, 34, 36, 36, 31, 32, 32, 31, 36, 31, 30 }

    1150

    Returns: 990031799

  86. {36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1, 36, 1 }

    300

    Returns: 487356020

  87. {2, 2 }

    4

    Returns: 1

  88. {36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 35, 36, 36, 35, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 35, 36, 36 }

    36

    Returns: 46656

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: