Statistics

Problem Statement for "ModEquationEasy"

Problem Statement

You are given the ints n, K, and v.

Consider the following modular equation with n variables: (x[0] * x[1] * x[2] * ... * x[n-1]) mod K = v. How many solutions does it have?

Formally, we want to find the number of sequences (x[0], x[1], ..., x[n-1]) such that each x[i] is an integer between 0 and K-1, inclusive, and the product of all x[i] gives the remainder v when divided by K.

Please compute and return the number of such sequences, modulo 10^9+7.

Definition

Class:
ModEquationEasy
Method:
count
Parameters:
int, int, int
Returns:
int
Method signature:
int count(int n, int K, int v)
(be sure your method is public)

Constraints

  • n will be between 1 and 1,000,000,000, inclusive.
  • K will be between 2 and 100, inclusive.
  • v will be between 0 and (K-1), inclusive.

Examples

  1. 2

    4

    1

    Returns: 2

    The input describes the modular equation (x[0] * x[1]) mod 4 = 1. There are two solutions: (1, 1) and (3, 3).

  2. 2

    4

    0

    Returns: 8

    This time we have 8 solutions: (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (2, 0), (3, 0) and (2, 2).

  3. 2

    4

    2

    Returns: 4

  4. 3

    7

    5

    Returns: 36

  5. 10

    100

    50

    Returns: 683036071

  6. 1

    2

    0

    Returns: 1

  7. 1000000000

    100

    73

    Returns: 829206200

  8. 1000000000

    97

    5

    Returns: 889032838

  9. 999999999

    75

    0

    Returns: 890108525

  10. 270376675

    81

    11

    Returns: 29849585

  11. 493987275

    65

    58

    Returns: 454782589

  12. 807762744

    79

    32

    Returns: 599118426

  13. 153978768

    84

    3

    Returns: 610164499

  14. 590322547

    30

    5

    Returns: 161141162

  15. 12990820

    60

    29

    Returns: 883842289

  16. 212157044

    43

    27

    Returns: 431311250

  17. 153047610

    62

    48

    Returns: 474828731

  18. 488132323

    30

    2

    Returns: 948652695

  19. 429379682

    47

    1

    Returns: 646509878

  20. 781043743

    18

    16

    Returns: 981549954

  21. 643246391

    86

    31

    Returns: 162138380

  22. 447637813

    64

    33

    Returns: 685760142

  23. 370299628

    44

    39

    Returns: 348219441

  24. 434767749

    78

    75

    Returns: 573439668

  25. 279758693

    85

    11

    Returns: 984254036

  26. 735025169

    20

    16

    Returns: 521071027

  27. 601803059

    15

    4

    Returns: 425867509

  28. 715803020

    50

    32

    Returns: 859083716

  29. 173432142

    99

    62

    Returns: 969937802

  30. 56606992

    29

    25

    Returns: 884155298

  31. 498825510

    94

    90

    Returns: 23327168

  32. 781352378

    58

    54

    Returns: 901495400

  33. 133726504

    38

    35

    Returns: 434396838

  34. 198741622

    65

    37

    Returns: 424348736

  35. 748842943

    49

    45

    Returns: 915088289

  36. 525546553

    94

    67

    Returns: 9707628

  37. 280381884

    14

    2

    Returns: 516295881

  38. 960248834

    10

    9

    Returns: 863905547

  39. 411866071

    89

    39

    Returns: 229224444

  40. 926793071

    5

    1

    Returns: 741283465

  41. 996432700

    82

    41

    Returns: 252802797

  42. 154513277

    40

    28

    Returns: 213635910

  43. 536362313

    52

    23

    Returns: 550944361

  44. 427480579

    20

    1

    Returns: 626091862

  45. 514926289

    89

    35

    Returns: 837422139

  46. 69035431

    76

    6

    Returns: 261641133

  47. 142886457

    28

    15

    Returns: 267277311

  48. 842167906

    51

    30

    Returns: 129592307

  49. 438972564

    33

    2

    Returns: 269383428

  50. 555830143

    95

    69

    Returns: 543369078

  51. 180534741

    19

    13

    Returns: 245277615

  52. 493505041

    35

    19

    Returns: 552643247

  53. 859102300

    33

    6

    Returns: 872099835

  54. 771021565

    27

    24

    Returns: 129229368

  55. 283942655

    31

    7

    Returns: 716202082

  56. 715267638

    68

    15

    Returns: 746989966

  57. 96575466

    83

    45

    Returns: 245513533

  58. 864817035

    76

    45

    Returns: 118751807

  59. 115601002

    65

    40

    Returns: 240945008

  60. 897298412

    6

    3

    Returns: 725845071

  61. 840017394

    47

    27

    Returns: 721450804

  62. 598781693

    14

    1

    Returns: 816518524

  63. 361589989

    3

    1

    Returns: 7950520

  64. 989014121

    37

    9

    Returns: 338682074

  65. 391900490

    55

    50

    Returns: 563291905

  66. 787160308

    99

    62

    Returns: 689519336

  67. 309399866

    54

    15

    Returns: 888941267

  68. 612889931

    46

    19

    Returns: 832124098

  69. 824118794

    24

    8

    Returns: 327122828

  70. 428204646

    83

    50

    Returns: 738189313

  71. 375251891

    46

    44

    Returns: 639922464

  72. 101326694

    29

    15

    Returns: 752988800

  73. 435600505

    25

    17

    Returns: 436729286

  74. 268111024

    53

    14

    Returns: 588763198

  75. 310358497

    93

    19

    Returns: 359884926

  76. 490937064

    44

    22

    Returns: 927057504

  77. 625841774

    98

    80

    Returns: 157555863

  78. 621332366

    44

    24

    Returns: 851869026

  79. 178316292

    37

    13

    Returns: 996533515

  80. 705724670

    41

    32

    Returns: 729608830

  81. 514385933

    100

    83

    Returns: 407142262

  82. 389525202

    99

    24

    Returns: 571927710

  83. 99611904

    45

    22

    Returns: 452355480

  84. 347026245

    34

    6

    Returns: 858926313

  85. 943165576

    87

    75

    Returns: 828345815

  86. 117450386

    11

    6

    Returns: 651413985

  87. 808133830

    57

    21

    Returns: 15430561

  88. 512229101

    28

    1

    Returns: 495546193

  89. 739124375

    5

    0

    Returns: 605281988

  90. 305255376

    56

    51

    Returns: 900878796

  91. 745337699

    65

    48

    Returns: 496983629

  92. 597000413

    61

    3

    Returns: 51154876

  93. 879582482

    92

    8

    Returns: 447789510

  94. 574301451

    54

    45

    Returns: 841447602

  95. 84847546

    79

    10

    Returns: 777209431

  96. 252828738

    43

    6

    Returns: 520666761

  97. 614040890

    68

    56

    Returns: 398794025

  98. 626153287

    83

    80

    Returns: 72958131

  99. 564358702

    51

    13

    Returns: 205133009

  100. 379745092

    79

    58

    Returns: 422326922

  101. 170771396

    30

    0

    Returns: 641397172

  102. 250608031

    89

    25

    Returns: 347087615

  103. 685263173

    95

    86

    Returns: 473902161

  104. 969837032

    87

    81

    Returns: 32726411

  105. 412500839

    17

    4

    Returns: 368394852

  106. 489767409

    67

    55

    Returns: 116690925

  107. 167310006

    95

    44

    Returns: 786561012

  108. 20018512

    35

    16

    Returns: 127030255

  109. 561580085

    64

    39

    Returns: 859006636

  110. 999999999

    100

    10

    Returns: 326729913

  111. 1000000000

    100

    99

    Returns: 829206200

  112. 1000000000

    87

    34

    Returns: 603756862

  113. 1000000000

    85

    0

    Returns: 227550486

  114. 1000000000

    88

    0

    Returns: 322370030

  115. 999999999

    100

    50

    Returns: 499596566

  116. 1000000000

    99

    9

    Returns: 731397752

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: