Statistics

Problem Statement for "Powerit"

Problem Statement

You are given three ints: n, k, and m.

For each i between 1 and n, inclusive, Fox Ciel calculated the number i^(2^k - 1). ("^" denotes exponentiation.)

Return the sum of all numbers Fox Ciel calculated, modulo m.

Definition

Class:
Powerit
Method:
calc
Parameters:
int, int, int
Returns:
int
Method signature:
int calc(int n, int k, int m)
(be sure your method is public)

Constraints

  • n will be between 1 and 1,000,000, inclusive.
  • k will be between 1 and 400, inclusive.
  • m will be between 2 and 1,000,000,000, inclusive.

Examples

  1. 4

    1

    107

    Returns: 10

  2. 4

    2

    107

    Returns: 100

    We have k=2 and therefore (2^k - 1) = (2^2 - 1) = 3. Fox Ciel calculated the numbers 1^3, 2^3, 3^3, and 4^3. Their sum is 100, and 100 modulo 107 is 100.

  3. 3

    3

    107

    Returns: 69

    The actual sum of Ciel's numbers is 2316, and 2316 modulo 107 is 69.

  4. 1

    400

    107

    Returns: 1

  5. 10

    2

    10

    Returns: 5

  6. 1000000

    400

    1000000000

    Returns: 0

  7. 3348

    3

    681318585

    Returns: 457999371

  8. 1134

    35

    411442879

    Returns: 334161548

  9. 2550

    38

    752795944

    Returns: 41572777

  10. 9589

    31

    470941272

    Returns: 86407945

  11. 6893

    32

    101410319

    Returns: 48696648

  12. 122

    36

    350817449

    Returns: 253006866

  13. 9114

    30

    66810926

    Returns: 6097469

  14. 5253

    37

    387142327

    Returns: 14139399

  15. 9711

    25

    351487933

    Returns: 330986031

  16. 9640

    15

    655422273

    Returns: 531550756

  17. 7401

    34

    572223950

    Returns: 130529351

  18. 8496

    33

    953318943

    Returns: 709306389

  19. 5656

    29

    481932956

    Returns: 44391236

  20. 3208

    30

    377693893

    Returns: 109500358

  21. 1886

    28

    262386486

    Returns: 54254331

  22. 3901

    26

    254045302

    Returns: 226500969

  23. 9993

    39

    985838476

    Returns: 785191165

  24. 9557

    39

    806222142

    Returns: 64303515

  25. 6423

    34

    994429285

    Returns: 672100621

  26. 9701

    28

    6730635

    Returns: 4501866

  27. 4282

    30

    631721722

    Returns: 446526461

  28. 9654

    11

    184029953

    Returns: 157767701

  29. 1722

    36

    845723778

    Returns: 287363997

  30. 9710

    34

    639192832

    Returns: 569635505

  31. 3301

    17

    856320826

    Returns: 352043513

  32. 9968

    19

    519501005

    Returns: 219340241

  33. 6277

    26

    319735517

    Returns: 75570271

  34. 9919

    37

    212474861

    Returns: 71748284

  35. 2832

    1

    23256828

    Returns: 4011528

  36. 9705

    33

    452667176

    Returns: 60815769

  37. 443348

    243

    681318585

    Returns: 71460036

  38. 981134

    395

    411442879

    Returns: 411185553

  39. 992550

    78

    752795944

    Returns: 32255401

  40. 309589

    271

    470941272

    Returns: 445542481

  41. 956893

    272

    101410319

    Returns: 87081909

  42. 770122

    196

    350817449

    Returns: 319256405

  43. 559114

    270

    66810926

    Returns: 40449977

  44. 495253

    317

    387142327

    Returns: 84570123

  45. 199711

    105

    351487933

    Returns: 187782517

  46. 579640

    175

    655422273

    Returns: 45860155

  47. 117401

    74

    572223950

    Returns: 233269251

  48. 218496

    140

    953318943

    Returns: 332327916

  49. 931311

    137

    963865910

    Returns: 812008126

  50. 639439

    204

    755387785

    Returns: 719937465

  51. 596795

    90

    524772971

    Returns: 295517558

  52. 768625

    86

    736875759

    Returns: 610788289

  53. 951108

    312

    568328429

    Returns: 302573945

  54. 596960

    17

    410703204

    Returns: 89978520

  55. 99053

    253

    112026146

    Returns: 22110685

  56. 398326

    22

    695843313

    Returns: 466856527

  57. 421603

    65

    280059370

    Returns: 253395356

  58. 576982

    12

    975512854

    Returns: 144332873

  59. 3158

    278

    764324232

    Returns: 239854833

  60. 611648

    236

    929523786

    Returns: 561897384

  61. 542013

    12

    325329334

    Returns: 219833757

  62. 611794

    32

    40776996

    Returns: 21686185

  63. 144259

    364

    688681983

    Returns: 469310449

  64. 869166

    208

    714073630

    Returns: 30880411

  65. 175719

    209

    257435394

    Returns: 33330492

  66. 86905

    372

    362572872

    Returns: 359566321

  67. 403470

    36

    815062262

    Returns: 294424755

  68. 411070

    388

    694715251

    Returns: 74979712

  69. 881650

    36

    74512798

    Returns: 5699443

  70. 741092

    222

    160427311

    Returns: 73852856

  71. 153127

    389

    251431445

    Returns: 125506469

  72. 269191

    397

    791499529

    Returns: 319676103

  73. 360321

    118

    342262793

    Returns: 182180507

  74. 513101

    87

    620897538

    Returns: 336725415

  75. 970890

    388

    294917169

    Returns: 251995749

  76. 412918

    400

    27318291

    Returns: 4380805

  77. 702568

    30

    147259731

    Returns: 128522716

  78. 694544

    389

    651490273

    Returns: 651116952

  79. 476266

    398

    942312155

    Returns: 851951051

  80. 818918

    386

    423200081

    Returns: 294881132

  81. 79960

    357

    784365917

    Returns: 188786291

  82. 262962

    319

    356218413

    Returns: 354775851

  83. 650976

    390

    51495091

    Returns: 46408023

  84. 710180

    389

    833079638

    Returns: 567811932

  85. 441938

    45

    678963665

    Returns: 444620086

  86. 65488

    9

    498462774

    Returns: 239473144

  87. 960999

    393

    705802158

    Returns: 274295838

  88. 968670

    389

    352976868

    Returns: 234233325

  89. 662315

    299

    499095705

    Returns: 136763070

  90. 995587

    369

    26695518

    Returns: 25640944

  91. 735365

    398

    372041885

    Returns: 19448015

  92. 987860

    393

    989078573

    Returns: 315562156

  93. 526871

    105

    95915719

    Returns: 73025674

  94. 973165

    253

    139772865

    Returns: 11561125

  95. 738435

    400

    485925430

    Returns: 246179010

  96. 982255

    400

    182342485

    Returns: 50301460

  97. 465706

    155

    315313015

    Returns: 173781556

  98. 982538

    348

    2210564

    Returns: 657037

  99. 631868

    394

    254085361

    Returns: 40085794

  100. 973904

    388

    870445961

    Returns: 360598799

  101. 587666

    281

    700188016

    Returns: 547270001

  102. 970080

    338

    267177703

    Returns: 61418075

  103. 177611

    398

    614526689

    Returns: 270778312

  104. 967308

    397

    440187978

    Returns: 241565838

  105. 363150

    370

    615727640

    Returns: 2979265

  106. 991098

    331

    743710051

    Returns: 99927372

  107. 760184

    398

    665419075

    Returns: 269844625

  108. 988925

    395

    361351719

    Returns: 241430421

  109. 580724

    360

    13676508

    Returns: 9397800

  110. 992274

    302

    408017968

    Returns: 211383745

  111. 597543

    392

    264859844

    Returns: 83323964

  112. 996298

    389

    269987261

    Returns: 60165552

  113. 196848

    37

    81269629

    Returns: 74853955

  114. 983425

    62

    927852680

    Returns: 569037745

  115. 681531

    387

    4111138

    Returns: 594622

  116. 987574

    400

    631047121

    Returns: 11465774

  117. 1000000

    1

    764411904

    Returns: 75114784

  118. 1000000

    2

    764411904

    Returns: 258688000

  119. 987654

    1

    1024000

    Returns: 529685

  120. 987987

    1

    536870912

    Returns: 43991070

  121. 987987

    2

    536870912

    Returns: 223544196

  122. 987987

    3

    536870912

    Returns: 71642284

  123. 987987

    4

    536870912

    Returns: 448603916

  124. 987987

    5

    536870912

    Returns: 392833228

  125. 987987

    400

    2

    Returns: 0

  126. 987987

    389

    5

    Returns: 4

  127. 999999

    399

    7

    Returns: 0

  128. 443348

    243

    364973499

    Returns: 325223910

  129. 716849

    6

    73629

    Returns: 22599

  130. 793139

    390

    75625

    Returns: 26775

  131. 681456

    105

    732050000

    Returns: 603877856

  132. 241915

    326

    310903351

    Returns: 78596521

  133. 497003

    283

    823851904

    Returns: 221427916

  134. 23785

    269

    1000

    Returns: 625

  135. 727138

    68

    643938125

    Returns: 201666176

  136. 609116

    242

    99

    Returns: 9

  137. 879028

    241

    766763811

    Returns: 136999099

  138. 869253

    366

    557646408

    Returns: 389122569

  139. 67108

    400

    91809

    Returns: 72433

  140. 937278

    202

    796953125

    Returns: 449092461

  141. 964228

    119

    100

    Returns: 16

  142. 477297

    387

    997353324

    Returns: 740571849

  143. 832276

    390

    448204933

    Returns: 250643145

  144. 754175

    264

    352218537

    Returns: 129774042

  145. 973141

    365

    536870912

    Returns: 196879689

  146. 863944

    5

    244140625

    Returns: 89034250

  147. 979811

    398

    664902216

    Returns: 548038764

  148. 448436

    111

    58564

    Returns: 0

  149. 980264

    344

    25

    Returns: 0

  150. 99865

    390

    796953125

    Returns: 191340650

  151. 995191

    394

    36663

    Returns: 30976

  152. 805758

    309

    25

    Returns: 16

  153. 9963

    1

    678410940

    Returns: 49635666

  154. 9949

    1

    668999740

    Returns: 49496275

  155. 9914

    1

    215841664

    Returns: 49148655

  156. 9923

    1

    238400932

    Returns: 49237926

  157. 9974

    1

    372984436

    Returns: 49745325

  158. 9907

    1

    19777264

    Returns: 9524750

  159. 9930

    1

    177681845

    Returns: 49307415

  160. 9910

    1

    760645136

    Returns: 49109005

  161. 9990

    1

    953843872

    Returns: 49905045

  162. 9974

    1

    630243632

    Returns: 49745325

  163. 9941

    2

    20339136

    Returns: 19897713

  164. 9913

    1

    720450280

    Returns: 49138741

  165. 9963

    1

    665652836

    Returns: 49635666

  166. 9995

    1

    208499500

    Returns: 49955010

  167. 9963

    1

    415502997

    Returns: 49635666

  168. 9994

    1

    225843959

    Returns: 49945015

  169. 9985

    1

    696416775

    Returns: 49855105

  170. 9979

    1

    942135424

    Returns: 49795210

  171. 9972

    1

    716976048

    Returns: 49725378

  172. 9977

    1

    439177752

    Returns: 49775253

  173. 9963

    1

    678410940

    Returns: 49635666

  174. 9949

    1

    668999740

    Returns: 49496275

  175. 9914

    1

    215841664

    Returns: 49148655

  176. 9923

    1

    238400932

    Returns: 49237926

  177. 9974

    1

    372984436

    Returns: 49745325

  178. 9907

    1

    19777264

    Returns: 9524750

  179. 9930

    1

    177681845

    Returns: 49307415

  180. 9910

    1

    760645136

    Returns: 49109005

  181. 9990

    1

    953843872

    Returns: 49905045

  182. 9974

    1

    630243632

    Returns: 49745325

  183. 9932

    141

    961

    Returns: 326

  184. 9967

    139

    9

    Returns: 7

  185. 9966

    141

    961

    Returns: 957

  186. 9922

    99

    18

    Returns: 7

  187. 9999

    99

    2

    Returns: 0

  188. 9970

    97

    2

    Returns: 1

  189. 9995

    99

    18

    Returns: 12

  190. 9932

    141

    961

    Returns: 326

  191. 9984

    97

    18

    Returns: 12

  192. 9923

    139

    9

    Returns: 3

  193. 999999

    400

    1000000000

    Returns: 0

  194. 1000000

    400

    2

    Returns: 0

  195. 1000000

    399

    1000007

    Returns: 501896

  196. 1000000

    400

    10000000

    Returns: 0

  197. 999999

    400

    999999999

    Returns: 504479016

  198. 1000000

    400

    100000000

    Returns: 0

  199. 1000

    400

    1000000

    Returns: 750000

  200. 938132

    382

    999998991

    Returns: 74187405

  201. 999997

    399

    536870911

    Returns: 183331312

  202. 2

    4

    3

    Returns: 0

  203. 1000000

    400

    999999999

    Returns: 504479017

  204. 1000000

    400

    99999999

    Returns: 68238226

  205. 1000000

    400

    1000

    Returns: 0

  206. 100000

    352

    1000

    Returns: 0

  207. 1000000

    400

    10

    Returns: 0

  208. 1000000

    400

    1111

    Returns: 606

  209. 111100

    400

    2

    Returns: 0

  210. 1000000

    400

    1007

    Returns: 815

  211. 1000000

    400

    57777

    Returns: 35407

  212. 999999

    399

    999999999

    Returns: 549167283

  213. 11000

    333

    888888

    Returns: 141504

  214. 1000000

    400

    100000099

    Returns: 49391523

  215. 1000

    3

    7

    Returns: 0

  216. 1000000

    400

    123456789

    Returns: 28311364

  217. 100002

    123

    123565

    Returns: 121844

  218. 987654

    399

    100000001

    Returns: 215596

  219. 999997

    400

    990000231

    Returns: 774897883

  220. 100000

    400

    4

    Returns: 0

  221. 999737

    377

    100000007

    Returns: 72349339

  222. 1000000

    400

    10000008

    Returns: 5972896

  223. 100000

    400

    2

    Returns: 0

  224. 1000000

    397

    555959447

    Returns: 277786381

  225. 1000000

    400

    100000015

    Returns: 32304705

  226. 3

    4

    15

    Returns: 6

  227. 1000

    400

    1000

    Returns: 0

  228. 5

    3

    9

    Returns: 3

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: