Nim | Topcoder Archive

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 a₁,...,a_K 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 a_i 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

```
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.
```
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.
```
10
```
```
100
```
```
Returns: 294844622
```
```
123456789
```
```
12345
```
```
Returns: 235511047
```

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.