WolfHockeyTeamEasy | Topcoder Archive

Problem Statement

The ice hockey season is almost over. Wolf Sothe and his teammates have asked Cat Snuke to take photos of their team.

There are 2*N wolves on the ice hockey team. The wolves are numbered from 0 to 2*N-1.

Cat Snuke is going to take photos of the whole team. The photos all have to look nice and they all have to look different. Both "nice" and "different" are formally defined below.

While taking each photo, the wolves will stand in a grid pattern with two rows by N columns. There is only one constraint: each row of the grid must contain a wolf whose number is K or more. Any such arrangement of wolves will look nice in a photo.

Given a photo of our 2*N wolves, we can look at it and write down a sequence of N+2 integers:

For each column (from the left to the right), write down the largest wolf number in that column.
Write down the largest wolf number in the first row.
Write down the largest wolf number in the second row.

Two photos are considered different if they produce different sequences.

You are given the ints N and K. Let X be the maximal number of nice and pairwise different photos Cat Snuke can take. Compute and return the value (X modulo 1,000,000,007).

Definition

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

Constraints

N will be between 1 and 1,000, inclusive.
K will be between 0 and 2N-1, inclusive.

Examples

```
2
```
```
0
```
```
Returns: 12
```
As N=2, we have four wolves. As K=0, each row of the grid must contain a wolf numbered 0 or more, which is always true. Hence, all 24 possible arrangements of wolves produce nice photos. However, some of those arrangements produce similar photos. For example, suppose there are wolves 1 and 2 in the first row and behind them wolves 0 and 3 in the second row. For this arrangement, we have: The maximum in the first column is max(1,0) = 1. The maximum in the second column is max(2,3) = 3. The maximum in the first row is max(1,2) = 2. The maximum in the second row is max(0,3) = 3. Hence, this arrangement produces the sequence {1,3,2,3}. Now suppose there are wolves 0 and 2 in the first row and wolves 1 and 3 in the second row. This is a different arrangement but it produces the same sequence: {1,3,2,3}. In total, Cat Snuke will be able to take at most 12 different photos. These correspond to the sequences {1,3,2,3}, {1,3,3,2}, {2,3,1,3}, {2,3,2,3}, {2,3,3,1}, {2,3,3,2}, {3,1,2,3}, {3,1,3,2}, {3,2,1,3}, {3,2,2,3}, {3,2,3,1}, and {3,2,3,2}.
```
4
```
```
5
```
```
Returns: 1104
```
```
100
```
```
120
```
```
Returns: 803057135
```
```
234
```
```
467
```
```
Returns: 0
```
Note that in this example K = 2*N-1. There is only one wolf with the number 2*N-1 or greater. Thus, in this case there are no nice photos: in one of the rows all wolves will always have numbers smaller than K.
```
810
```
```
893
```
```
Returns: 281618909
```

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.