Statistics

Problem Statement for "PowerPartition"

Problem Statement

Yayoi and Iori like traveling together. One day, they arrived to a strange planet. The currency system on the planet is really simple: the denominations are precisely all nonnegative powers of an integer M. I.e., the coins have the following values: 1, M, M^2, M^3, ...

Yayoi and Iori now want to buy souvenirs for their friends. The total price of those souvenirs is X. Yayoi and Iori would like to pay this amount exactly. They have a sufficient supply of coins with each of the available values.

You are given the int M and the long X. Let W be the number of different ways in which they can pay the required amount. Here, two ways are considered different if and only if there is some value such that in each way we use a different number of coins with this value. As W can be huge, return the value (W modulo 1,000,000,007).

Definition

Class:
PowerPartition
Method:
count
Parameters:
int, long
Returns:
int
Method signature:
int count(int M, long X)
(be sure your method is public)

Constraints

  • M will be between 2 and 1000, inclusive.
  • X will be between 1 and 10^18, inclusive.

Examples

  1. 2

    4

    Returns: 4

    The coins have values 1, 2, 4, 8, 16, etc. The amount Yayoi and Iori want to pay is 4. There are four different ways to do that: 4, 2+2, 2+1+1, and 1+1+1+1.

  2. 17

    1

    Returns: 1

    The price of souvenirs is only 1. There is only one way to pay this amount: by using a single coin with value 1.

  3. 1000

    1000000007

    Returns: 500501002

  4. 841

    765346961765346961

    Returns: 89045497

  5. 2

    1

    Returns: 1

  6. 2

    2

    Returns: 2

  7. 2

    3

    Returns: 2

  8. 2

    4

    Returns: 4

  9. 2

    576460752303423488

    Returns: 16647759

  10. 2

    1000000000000000000

    Returns: 979665583

  11. 3

    1000000000000000000

    Returns: 511490316

  12. 4

    1000000000000000000

    Returns: 63286154

  13. 10

    1000000000000000000

    Returns: 239242151

  14. 100

    1000000000000000000

    Returns: 846316327

  15. 334

    1000000000000000000

    Returns: 189656550

  16. 114

    1000000000000000000

    Returns: 483823521

  17. 514

    1000000000000000000

    Returns: 207890258

  18. 810

    1000000000000000000

    Returns: 833081743

  19. 893

    1000000000000000000

    Returns: 262776600

  20. 999

    1000000000000000000

    Returns: 822069591

  21. 1000

    1000000000000000000

    Returns: 911670813

  22. 4

    1

    Returns: 1

  23. 4

    2

    Returns: 1

  24. 4

    3

    Returns: 1

  25. 4

    4

    Returns: 2

  26. 4

    5

    Returns: 2

  27. 4

    6

    Returns: 2

  28. 10

    1234567890

    Returns: 185701495

  29. 5

    314159265358979323

    Returns: 274523856

  30. 571

    2831

    Returns: 5

  31. 298

    4478

    Returns: 16

  32. 996

    4260

    Returns: 5

  33. 376

    28850

    Returns: 77

  34. 127

    13108

    Returns: 104

  35. 675

    7318

    Returns: 11

  36. 870

    7849

    Returns: 10

  37. 513

    13442

    Returns: 27

  38. 799

    8747

    Returns: 11

  39. 819

    24316

    Returns: 30

  40. 20

    348762283806698400

    Returns: 770425042

  41. 719

    53974711195664384

    Returns: 226452326

  42. 681

    857588607656402944

    Returns: 592479968

  43. 638

    549204957015310336

    Returns: 701189860

  44. 7

    484655331968694272

    Returns: 729217017

  45. 149

    803072246364561408

    Returns: 361439461

  46. 48

    189643710351648704

    Returns: 13472139

  47. 281

    986198085408077708

    Returns: 959502702

  48. 615

    513398561082321920

    Returns: 621862727

  49. 289

    659814431560352000

    Returns: 298083419

  50. 3

    111210166595878912

    Returns: 194527775

  51. 3

    942708822413332480

    Returns: 329378396

  52. 3

    338154468263032576

    Returns: 497880243

  53. 3

    295779622906652928

    Returns: 993689261

  54. 2

    883846780649838592

    Returns: 54548851

  55. 3

    661439914500912128

    Returns: 375593451

  56. 6

    706288342011703552

    Returns: 883051307

  57. 5

    332065875927580672

    Returns: 425045334

  58. 6

    750054119236400512

    Returns: 157272746

  59. 3

    796112076860178048

    Returns: 591060666

  60. 2

    576460752303423487

    Returns: 196043654

  61. 3

    450283905890997363

    Returns: 205899899

  62. 3

    450283905890997362

    Returns: 473737494

  63. 10

    999999999999999999

    Returns: 903166439

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: