Statistics

Problem Statement for "PenguinEmperor"

Problem Statement

Percy would like to become the Penguin Emperor. First, he must go on a long journey to prove himself worthy.


There are several cities in Penguin Empire. All the cities lie on a circle around the great mountain. The cities are numbered 0 through numCities-1 in the clockwise direction around the mountain.


Percy lives in city 0 and that is where he will begin his journey. On the first day he will travel to a city adjacent to city 0. On the second day he will travel to another city two cities away from his current city. And so on: for each k, on the k-th day he will travel to a new city k cities away. Each day, Percy can choose a new direction of travel: either clockwise or counter-clockwise around the mountain.



You are given the int numCities representing the number of cities in the Penguin Empire. You are also given a long daysPassed representing the number of days that have passed since Percy's journey began. Compute and return the number of journeys that take daysPassed days and return home to city 0. Two journeys are considered different if there is some k such that after k days the traveler is in different cities. As the number of journeys can be quite large, please return the result modulo 1,000,000,007.

Definition

Class:
PenguinEmperor
Method:
countJourneys
Parameters:
int, long
Returns:
int
Method signature:
int countJourneys(int numCities, long daysPassed)
(be sure your method is public)

Constraints

  • numCities will be between 2 and 350, inclusive.
  • daysPassed will be between 1 and 10^18, inclusive.

Examples

  1. 3

    2

    Returns: 2

    There are two ways to have a Journey that returns home after two days. 0 -> 1 -> 0 where directions are CW-CW 0 -> 2 -> 0 where directions are CCW-CCW CW = clockwise CCW = counter-clockwise

  2. 4

    3

    Returns: 2

    There are two ways to have a Journey that returns home after three days. 0 -> 1 -> 3 -> 0 where directions are CW-CW-CCW or CW-CCW-CCW 0 -> 3 -> 1 -> 0 where directions are CCW-CCW-CW or CWW-CW-CW CW = clockwise CCW = counter-clockwise

  3. 5

    36

    Returns: 107374182

  4. 300

    751

    Returns: 413521250

  5. 300

    750

    Returns: 0

  6. 350

    1000000000000000000

    Returns: 667009739

  7. 5

    7

    Returns: 12

  8. 350

    576460752303423487

    Returns: 157219053

  9. 51

    3453

    Returns: 681882592

  10. 350

    51

    Returns: 304806205

  11. 323

    1

    Returns: 0

  12. 323

    3

    Returns: 2

  13. 323

    4

    Returns: 2

  14. 323

    5

    Returns: 0

  15. 2

    576460752303423487

    Returns: 1

  16. 2

    1000000000000000000

    Returns: 1

  17. 2

    100000000001

    Returns: 0

  18. 3

    100010100101

    Returns: 301669435

  19. 350

    788129934789836450

    Returns: 0

  20. 349

    785878134976151203

    Returns: 909056360

  21. 2

    1

    Returns: 0

  22. 32

    213412342314123

    Returns: 453664493

  23. 342

    12341243

    Returns: 697501401

  24. 333

    1212121212

    Returns: 27013629

  25. 350

    350

    Returns: 0

  26. 350

    349

    Returns: 0

  27. 350

    351

    Returns: 310756132

  28. 2

    2

    Returns: 0

  29. 2

    3

    Returns: 1

  30. 2

    4

    Returns: 1

  31. 7

    1234132481234323

    Returns: 642755153

  32. 347

    781374535348780709

    Returns: 359419672

  33. 349

    233

    Returns: 713040368

  34. 201

    514496860578435780

    Returns: 988139060

  35. 310

    883890419249926660

    Returns: 667056628

  36. 116

    824378772965568000

    Returns: 740196544

  37. 85

    744833315135881860

    Returns: 524391913

  38. 91

    431567805524141440

    Returns: 418233654

  39. 88

    602506188315165180

    Returns: 860373109

  40. 58

    454737952532060860

    Returns: 260070945

  41. 253

    130164509677965216

    Returns: 703374640

  42. 290

    30793709076387564

    Returns: 947227231

  43. 246

    745643484792426110

    Returns: 0

  44. 200

    25112172927

    Returns: 847767337

  45. 259

    10012503288

    Returns: 12258986

  46. 120

    43118587248

    Returns: 716761497

  47. 222

    18539410826

    Returns: 0

  48. 251

    65088042107

    Returns: 495673673

  49. 322

    1269521214

    Returns: 0

  50. 262

    8361710989

    Returns: 0

  51. 150

    16177337542

    Returns: 0

  52. 146

    38480129952

    Returns: 221033522

  53. 224

    11954975280

    Returns: 189460651

  54. 15

    79056

    Returns: 601920383

  55. 45

    63574

    Returns: 500990433

  56. 201

    98166

    Returns: 300815399

  57. 51

    80799

    Returns: 703272657

  58. 244

    55390

    Returns: 0

  59. 5

    38316

    Returns: 354237861

  60. 124

    79552

    Returns: 716073185

  61. 189

    12685

    Returns: 271261413

  62. 130

    43068

    Returns: 923988205

  63. 29

    57228

    Returns: 38437960

  64. 338

    206

    Returns: 0

  65. 123

    738

    Returns: 333944189

  66. 78

    376

    Returns: 609529593

  67. 142

    485

    Returns: 0

  68. 82

    274

    Returns: 0

  69. 319

    392

    Returns: 811077399

  70. 36

    739

    Returns: 504483063

  71. 197

    733

    Returns: 341708807

  72. 229

    980

    Returns: 387321373

  73. 177

    605

    Returns: 604034094

  74. 51

    51

    Returns: 468609660

  75. 350

    999999999999999999

    Returns: 921915152

  76. 350

    394064967394918050

    Returns: 0

  77. 349

    1000000000000000000

    Returns: 96071113

  78. 350

    788129934789836799

    Returns: 861127998

  79. 350

    985162418487295950

    Returns: 0

  80. 3

    3

    Returns: 2

  81. 350

    98516241848729250

    Returns: 0

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: