AlienAndSetDiv2 | Topcoder Archive

Problem Statement

Alien Fred wants to destroy the Earth. But before he does that, he wants to solve the following problem.

He has the set {1, 2, 3, ..., 2N}. He wants to split this set into two new sets A and B. The following conditions must all be satisfied:

Each element of the original set must belong to exactly one of the sets A and B.
The two new sets must have the same size. (I.e., each of them must contain exactly N numbers.)
For each i from 1 to N, inclusive: Let A[i] be the i-th smallest element of A, and let B[i] be the i-th smallest element of B. The difference |A[i] - B[i]| must be less than or equal to K.

You are given the two ints N and K. Let X be the total number of ways in which Fred can choose the sets A and B. Return the value (X modulo 1,000,000,007).

Definition

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

Constraints

N will be between 1 and 50, inclusive.
K will be between 1 and 10, inclusive.

Examples

```
2
```
```
1
```
```
Returns: 4
```
The initial set is {1, 2, 3, 4}. The following 6 pairs of subsets are possible in this case: A={1, 2} and B={3, 4} A={1, 3} and B={2, 4} A={1, 4} and B={2, 3} A={2, 3} and B={1, 4} A={2, 4} and B={1, 3} A={3, 4} and B={1, 2} The first option and the last option are both invalid. One of the reasons is that in both cases the difference between the smallest element in A and the smallest element in B is too large (3-1 = 2, which is more than 1). The other 4 options are valid. Note that order of the two sets matters: the option A={1,3} and B={2,4} differs from the option A={2,4} and B={1,3}.
```
3
```
```
1
```
```
Returns: 8
```
```
4
```
```
2
```
```
Returns: 44
```
```
10
```
```
10
```
```
Returns: 184756
```

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.