Statistics

Problem Statement for "Nim"

Problem Statement

Alice and Bob are going to play a famous game called Nim. In the game Nim, first they set up stones in K piles containing a1,...,aK stones respectively. Then they alternatively take turns (Alice moves first). On a player's turn the player chooses a pile and takes some (at least one) stones from that pile. If there are no piles left which contain any stones, the player loses.

Since they like prime numbers very much, they decided to make each ai a prime number less than or equal to L. Given K and L return the number of such initial setups which allows Bob to win, assuming they play optimally, modulo 1,000,000,007.

Definition

Class:
Nim
Method:
count
Parameters:
int, int
Returns:
int
Method signature:
int count(int K, int L)
(be sure your method is public)

Notes

  • Two setups are considered different if at least one ai is different between them (for example, (a1,a2,a3)=(2,5,7) and (2,7,5) are considered different).

Constraints

  • K will be between 1 and 1000000000(=10^9), inclusive.
  • L will be between 2 and 50000, inclusive.

Examples

  1. 3

    7

    Returns: 6

    Prime numbers <= 7 are 2, 3, 5 and 7. Bob can win if the initial setup is (2,5,7) or its permutation. So return 3! = 6.

  2. 4

    13

    Returns: 120

    Bob can win if the initial setup is (p,p,p,p) for some prime p<=13, (p,p,q,q) or its permutation for p<q<=13, or (3,5,11,13) or its permutation. So return 6+(6C2*6)+4!=6+90+24=120.

  3. 10

    100

    Returns: 294844622

  4. 123456789

    12345

    Returns: 235511047

  5. 1000000000

    50000

    Returns: 428193537

  6. 536870911

    50000

    Returns: 876223480

  7. 851074452

    2

    Returns: 1

  8. 730089759

    2

    Returns: 0

  9. 1

    40896

    Returns: 0

  10. 47019195

    34646

    Returns: 934738423

  11. 28936827

    7782

    Returns: 40794182

  12. 15812775

    27956

    Returns: 283434976

  13. 190196934

    14059

    Returns: 123197951

  14. 716672276

    38338

    Returns: 882439375

  15. 564627688

    40604

    Returns: 665233567

  16. 551590996

    22234

    Returns: 363992923

  17. 501224365

    44457

    Returns: 11964323

  18. 750221573

    36803

    Returns: 555800014

  19. 122533725

    19341

    Returns: 975271918

  20. 227305387

    38046

    Returns: 971447731

  21. 565831594

    2631

    Returns: 268604770

  22. 481490246

    13783

    Returns: 757550261

  23. 228141633

    36534

    Returns: 485594440

  24. 54449353

    9112

    Returns: 91977500

  25. 194584965

    19828

    Returns: 308223866

  26. 550322371

    45058

    Returns: 244221498

  27. 171797431

    34438

    Returns: 323320897

  28. 281798688

    7792

    Returns: 852963488

  29. 321381352

    10171

    Returns: 428007308

  30. 85887988

    4263

    Returns: 683469806

  31. 323770191

    45291

    Returns: 982869581

  32. 699092237

    28631

    Returns: 736598097

  33. 16549543

    34382

    Returns: 985165586

  34. 767705040

    32768

    Returns: 547625054

  35. 666736613

    27191

    Returns: 22019280

  36. 31716843

    22317

    Returns: 733222216

  37. 365187752

    2470

    Returns: 606299899

  38. 481611498

    49584

    Returns: 575100255

  39. 668594414

    16577

    Returns: 144766160

  40. 387434732

    16918

    Returns: 94933056

  41. 766926204

    41335

    Returns: 879472853

  42. 904008961

    3484

    Returns: 243215073

  43. 458414142

    13935

    Returns: 322381875

  44. 341109512

    41310

    Returns: 334115532

  45. 505789848

    44167

    Returns: 28677620

  46. 10679065

    43320

    Returns: 629488938

  47. 953574649

    41567

    Returns: 5594684

  48. 43207634

    12019

    Returns: 332758612

  49. 398226368

    47292

    Returns: 472446227

  50. 873001961

    22611

    Returns: 951945451

  51. 373230639

    28921

    Returns: 67506826

  52. 745069818

    27514

    Returns: 209099483

  53. 334207492

    26341

    Returns: 583664177

  54. 358114336

    46180

    Returns: 492261604

  55. 953932640

    22668

    Returns: 463193303

  56. 319284696

    7511

    Returns: 956907403

  57. 49192562

    28763

    Returns: 601521510

  58. 249031141

    34952

    Returns: 658152522

  59. 211399923

    13944

    Returns: 884881845

  60. 845326618

    41943

    Returns: 506577188

  61. 955614049

    43395

    Returns: 741376939

  62. 910405120

    46728

    Returns: 997288401

  63. 814826499

    41505

    Returns: 955918704

  64. 858808349

    41094

    Returns: 527296394

  65. 911564481

    48531

    Returns: 585709562

  66. 953774422

    49539

    Returns: 74925937

  67. 866980373

    45595

    Returns: 740963104

  68. 812971224

    43152

    Returns: 844436000

  69. 964955356

    47010

    Returns: 400946565

  70. 2

    50000

    Returns: 5133

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: