TheCowDivOne | Topcoder Archive

Problem Statement

Farmer John had N cows numbered 0 to N-1. One day he saw K cows running away from his farm. Fox Brus computed the sum of the numbers of the escaped cows. She only told John that the sum was divisible by N.

Your task is to help John by counting the number of possible sets of escaped cows. This number may be very big, so return it modulo 1,000,000,007.

Definition

Class:: TheCowDivOne
Method:: find
Parameters:: int, int
Returns:: int
Method signature:: int find(int N, int K)
(be sure your method is public)

Constraints

N will be between 1 and 1,000,000,000, inclusive.
K will be between 1 and 1,000, inclusive.
K will be less than or equal to N.

Examples

```
7
```
```
4
```
```
Returns: 5
```
7 cows are numbered 0 to 6 and 4 of them run away. Possible sets of escaped cows are {0, 1, 2, 4}, {0, 3, 5, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {2, 3, 4, 5}.
```
1
```
```
1
```
```
Returns: 1
```
```
58
```
```
4
```
```
Returns: 7322
```
```
1000
```
```
47
```
```
Returns: 219736903
```
```
1000000000
```
```
1000
```
```
Returns: 666683069
```

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.