Statistics

Problem Statement for "PrettyPrimes"

Problem Statement

Time limit is 4 seconds.


All numbers in this problem are positive integers in base 10 with no leading zeros.

We are interested in occurrences of a number in another number. This happens whenever the string of digits that represents the first number occurs in the string of digits that represents the second number (as a contiguous subsequence).

For example:

  • There are two occurrences of 47 in 147000470.
  • There is one occurrence of 47 in 47.
  • There are no occurrences of 47 in 3.
  • There are no occurrences of 42 in 4002.
  • There are three occurrences of 33 in 133337. (Note that there are three occurrences, not just two. Occurrences may overlap.)

You are given an int pattern with at most two digits and an int D.

Let S be the set of all D-digit prime numbers with the maximum number of occurrences of the given pattern.

Return sum(S) modulo 1,000,000,007.

Definition

Class:
PrettyPrimes
Method:
solve
Parameters:
int, int
Returns:
int
Method signature:
int solve(int pattern, int D)
(be sure your method is public)

Constraints

  • pattern will be between 1 and 99, inclusive.
  • D will be between 1 and 12, inclusive.

Examples

  1. 17

    5

    Returns: 125285

    Clearly we can get at most two occurrences of 17 in a 5-digit number. There are five 5-digit primes with two occurrences of the number 17. These are 11717, 17117, 17317, 17417, and 61717. The answer is their sum.

  2. 42

    5

    Returns: 12818536

    There are no primes with two occurrences of 42. There are 258 primes with one occurrence of 42. The smallest among them is 10427, the largest one is 98429. The answer is their sum.

  3. 44

    10

    Returns: 444444419

    The only 10-digit number with 9 occurrences of 44 is clearly not a prime. The only 10-digit number with 8 occurrences of 44 is 4,444,444,447. The answer is this number modulo 10^9 + 7.

  4. 14

    1

    Returns: 17

    The 1-digit primes with the most occurrences of the number 14 are the primes 2, 3, 5, and 7. Each of them contains zero occurrences of the number 14.

  5. 6

    1

    Returns: 17

  6. 5

    1

    Returns: 5

  7. 1

    2

    Returns: 11

  8. 3

    2

    Returns: 356

  9. 85

    11

    Returns: 843839847

  10. 82

    11

    Returns: 380458850

  11. 94

    11

    Returns: 219009470

  12. 99

    12

    Returns: 593455582

  13. 90

    11

    Returns: 661728243

  14. 83

    12

    Returns: 299463482

  15. 60

    2

    Returns: 1043

  16. 70

    9

    Returns: 139332867

  17. 80

    10

    Returns: 143937998

  18. 60

    5

    Returns: 121208

  19. 90

    7

    Returns: 9090901

  20. 70

    10

    Returns: 987967513

  21. 10

    7

    Returns: 154767039

  22. 10

    2

    Returns: 1043

  23. 10

    5

    Returns: 10103

  24. 80

    12

    Returns: 204276999

  25. 90

    1

    Returns: 17

  26. 60

    10

    Returns: 344458951

  27. 70

    4

    Returns: 122100

  28. 40

    9

    Returns: 808080810

  29. 90

    6

    Returns: 20343188

  30. 80

    4

    Returns: 150440

  31. 10

    9

    Returns: 26180870

  32. 60

    12

    Returns: 343807270

  33. 60

    10

    Returns: 344458951

  34. 60

    9

    Returns: 606060607

  35. 44

    4

    Returns: 8888

  36. 11

    3

    Returns: 2357

  37. 66

    2

    Returns: 1043

  38. 66

    10

    Returns: 666666619

  39. 77

    9

    Returns: 355555543

  40. 99

    5

    Returns: 289988

  41. 22

    11

    Returns: 222222069

  42. 44

    12

    Returns: 444441335

  43. 66

    4

    Returns: 6661

  44. 88

    12

    Returns: 888882671

  45. 22

    7

    Returns: 41333703

  46. 66

    11

    Returns: 666666205

  47. 55

    4

    Returns: 5557

  48. 99

    5

    Returns: 289988

  49. 66

    9

    Returns: 666666667

  50. 11

    8

    Returns: 154444458

  51. 55

    10

    Returns: 555555522

  52. 77

    5

    Returns: 291104

  53. 99

    4

    Returns: 18996

  54. 22

    11

    Returns: 222222069

  55. 4

    7

    Returns: 187966743

  56. 8

    5

    Returns: 88883

  57. 9

    3

    Returns: 5133

  58. 8

    1

    Returns: 17

  59. 3

    9

    Returns: 711465630

  60. 2

    2

    Returns: 52

  61. 5

    9

    Returns: 347282750

  62. 9

    8

    Returns: 99396930

  63. 7

    6

    Returns: 8510217

  64. 1

    10

    Returns: 882626517

  65. 5

    11

    Returns: 254057974

  66. 9

    11

    Returns: 489157372

  67. 8

    12

    Returns: 888882671

  68. 6

    1

    Returns: 17

  69. 4

    4

    Returns: 8888

  70. 6

    7

    Returns: 267152609

  71. 3

    3

    Returns: 3489

  72. 8

    4

    Returns: 8887

  73. 3

    2

    Returns: 356

  74. 3

    12

    Returns: 648057607

  75. 69

    7

    Returns: 29540467

  76. 25

    8

    Returns: 463500897

  77. 12

    7

    Returns: 1212121

  78. 26

    1

    Returns: 17

  79. 51

    3

    Returns: 1153

  80. 39

    8

    Returns: 833118626

  81. 48

    9

    Returns: 748653964

  82. 81

    12

    Returns: 175438749

  83. 23

    3

    Returns: 2041

  84. 96

    11

    Returns: 969696289

  85. 14

    12

    Returns: 308862652

  86. 17

    2

    Returns: 17

  87. 12

    5

    Returns: 9951144

  88. 19

    5

    Returns: 160195

  89. 49

    3

    Returns: 1937

  90. 95

    10

    Returns: 404781019

  91. 28

    6

    Returns: 8900938

  92. 91

    2

    Returns: 1043

  93. 65

    10

    Returns: 942556139

  94. 83

    2

    Returns: 83

  95. 92

    8

    Returns: 930364643

  96. 81

    7

    Returns: 64817429

  97. 92

    5

    Returns: 185848

  98. 89

    2

    Returns: 89

  99. 46

    6

    Returns: 9579592

  100. 38

    1

    Returns: 17

  101. 28

    8

    Returns: 809621903

  102. 59

    11

    Returns: 448109208

  103. 19

    4

    Returns: 240043

  104. 51

    5

    Returns: 205730

  105. 98

    7

    Returns: 775795978

  106. 98

    9

    Returns: 979797965

  107. 65

    7

    Returns: 201388382

  108. 42

    2

    Returns: 1043

  109. 95

    7

    Returns: 578247193

  110. 69

    6

    Returns: 41372158

  111. 76

    1

    Returns: 17

  112. 61

    7

    Returns: 37983727

  113. 45

    4

    Returns: 102579

  114. 85

    8

    Returns: 813998849

  115. 1

    12

    Returns: 846432860

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: